Problem 92: Reverse Linked List II
思路
1. 找到四个关键点
2. m 到 n 反转
3. 拼接
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || m >= n) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
for (int i = 1; i < m; i++) {
if (head == null) return null;
head = head.next;
}
ListNode premNode = head;
ListNode mNode = head.next;
ListNode nNode = mNode;
ListNode postNode = nNode.next;
for (int i = m; i < n; i++) {
if (postNode == null) return null;
ListNode tmp = postNode.next;
postNode.next = nNode;
nNode = postNode;
postNode = tmp;
}
mNode.next = postNode;
premNode.next = nNode;
return dummy.next;
}
}
易错点
建立dummy node
ListNode dummy = new ListNode(0); dummy.next = head; head = dummy;
移动到 m 点处
for (int i = 1; i < m; i++) { if (head == null) { return null; } head = head.next; }
注意:这里是从 1 到 m,一共是 (m - 1)次移动。
reverse
ListNode temp = postnNode.next; postnNode.next = nNode; nNode = postnNode; postnNode = temp;




Last updated
Was this helpful?