92. Reverse Linked List II
Problem:
第三遍是自己想出来的one pass。
主要是搞清楚怎么把m 到n reverse过后的头和尾和原链表链接起来。
12/21/2017 update
The last step is the most import part of this problem. Don't forget it.
-------------------------------------------------------------------------------
思路:
找到m-1节点,保存下来,相当于子链表的dummy。然后从m开始,reverse n-m次。初始化prev在m上,cur 在m.next上。reverse结束后,prev在n上,cur在n.next上。最后重新连接链表。
做了这道题和reserve nodes in k-group才真正掌握了dummy node相关题目。
reverse过程如下图:
实现:
九章的解法太复杂了。需要的临时节点太多容易出错。代码如下:
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL5/1/2017 update:
第三遍是自己想出来的one pass。
主要是搞清楚怎么把m 到n reverse过后的头和尾和原链表链接起来。
class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; ListNode beforeM = null; for (int i = 0; i < m - 1; i++) { prev = prev.next; } beforeM = prev; prev = prev.next; ListNode cur = prev.next, tail = prev; for (int i = 0; i < n - m; i++) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } beforeM.next = prev; tail.next = cur; return dummy.next; } }
12/21/2017 update
The last step is the most import part of this problem. Don't forget it.
-------------------------------------------------------------------------------
思路:
找到m-1节点,保存下来,相当于子链表的dummy。然后从m开始,reverse n-m次。初始化prev在m上,cur 在m.next上。reverse结束后,prev在n上,cur在n.next上。最后重新连接链表。
做了这道题和reserve nodes in k-group才真正掌握了dummy node相关题目。
reverse过程如下图:
实现:
九章的解法太复杂了。需要的临时节点太多容易出错。代码如下:
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// write your code here
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
for(int i = 0; i < m-1; i++) {
head = head.next;
}
ListNode prev = head.next;
ListNode cur = prev.next;
for(int i = 0; i < n-m; i++) {
ListNode temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
head.next.next = cur;
head.next = prev;
return dummy.next;
}
}
评论
发表评论