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:**

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