Leetcode: Reverse Linked List II

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.

Understand the problem:
The problem asks for reversing a linked list from position m to n. Note that 1 <= m <= n <= length. The problem also requires for in-place and one-pass traversal of the linked list. 

Solution:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) {  *         val = x;  *         next = null;  *     }  * }  */ public class Solution {     public ListNode reverseBetween(ListNode head, int m, int n) {         if (head == null || head.next == null || m == n) {             return head;         }                   ListNode dummyNode = new ListNode(0);         dummyNode.next = head;         head = dummyNode;                   ListNode prev = dummyNode;         ListNode start = dummyNode.next;         ListNode end = dummyNode.next;                   // move end pointer n - m steps ahead;         for (int i = 0; i < n - m; i++) {             end = end.next;         }                   // move all the three pointers to m - 1 steps         for (int i = 0; i < m - 1; i++) {             prev = prev.next;             start = start.next;             end = end.next;         }                   ListNode nextNode = end.next;         end.next = null;                   // Reverse linked list from start to end         ListNode newHead = reverseList(start);                   prev.next = newHead;                           start.next = nextNode;                   return dummyNode.next;     }           private ListNode reverseList(ListNode head) {         ListNode prev = null;         ListNode curr= head;                   while (curr != null) {             ListNode nextNode = curr.next;                           curr.next = prev;             prev = curr;                           curr = nextNode;         }                   return prev;     } }

Update 10/8/14:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) {  *         val = x;  *         next = null;  *     }  * }  */ public class Solution {     public ListNode reverseBetween(ListNode head, int m, int n) {         if (head == null || head.next == null || m == n) {             return head;         }                   ListNode dummyNode = new ListNode(0);         dummyNode.next  = head;                   int count = 1;         /// Find the tail node of the first segment         ListNode firstTail = dummyNode;         while (count < m) {             firstTail = firstTail.next;             count++;         }                   /// reverse the middle segement         ListNode midTail = firstTail.next;         ListNode midHead = firstTail.next;                   ListNode prev = null;         int num = n - m + 1;         int i = 0;         while (i < num) {             ListNode next = midHead.next;             midHead.next = prev;             prev = midHead;             midHead = next;             i++;         }                   /// Link with the third segment         firstTail.next = prev;         midTail.next = midHead;                   return dummyNode.next;               } }