首页 > 代码库 > [LeetCode#92]Reverse Linked List II
[LeetCode#92]Reverse Linked List II
The problem:
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL
, m = 2 and n = 4,
return 1->4->3->2->5->NULL
.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
My analysis:
The mainipulation over Linkedlist involves many skills!!!1. proper use the dummy head to avoid the corner case over the first node. ListNode dummy = new ListNode(1);dummy.next = head;ListNode pre = dummy;By using the dummy head, even the m is 1(which means the first node), we could have a pre pointer for any nodes in the linkedlist. Thus when "m = 1", we could still use the same invariant.2. How to move to the right node?Differ from the indexing method in array, requires us must start from the first node. the index method used in linkedlist is very flexible. Thus, we should understand very clear about the while loop and counting!!!Usually, we use following invariant of while loop:Assume the node temp is currently at the index m, if we need to reach the n node starting from it.1 int i = m;2 while (temp.next != null && i < n) {3 temp = temp.next;4 i++;5 }6 if (i < n) return not foundAnalysis:When we exit from the while loop(step 5), the current position is ith node. Apparently, the checking condition "i < n" would be violated when i = n. that means the current i‘s value is n, indicates we are at the nth node!!!Note: we usually do other things in the while loop. 1 int i = m;2 while (temp.next != null && i < n) { other things ... ....3 temp = temp.next;4 i++;5 }6 if (i < n) return not found; //if (i < n) could use to check iff the linkedlist really have nth node.In this situation, we just reach the nth node, but the nth node doesn‘t enter into the while loop, so was not go through other things in the while loop.(the nth node was not processed). in order to let the nth node be processed, we need to change the loop condition into "while (temp.next != null && i < n + 1)" or "while (temp.next != null && i <= n)" .3.Clarification:while (i < n) {} seems not be able to reach the nth node?The i is actually use to indicate pre pointer‘s location(virtuallly). when the pre reached the nth node, it stop(notr proceed), thus only n-1 node poninted by the pre pointer enter the loop. What‘s more, since the we start from pre(pre = dummy), in fact only n-2 th node pointed by the prepointer enter the loop. But cur = pre.next.next. Thus, the cur actually reached the n+1th node, and nth node was the last node enter into the loop. Those understanding are very important!!! You must master it!
The solution:
public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (head == null) return head; ListNode dummy = new ListNode(1); dummy.next = head; ListNode pre = dummy; ListNode cur; ListNode m_node; ListNode next; int i = 1; while (pre.next != null && i < m) { pre = pre.next; i++; } if (i < m) return head; m_node = pre.next; cur = m_node.next; while (i < n) { next = cur.next; cur.next = pre.next; pre.next = cur; m_node.next = next; cur = next; i++; } return dummy.next; }}
[LeetCode#92]Reverse Linked List II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。