Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given
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:Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
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:
/** * 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:
/** * 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; } }
No comments:
Post a Comment