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.
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
Solution: Maintain three parts: head to t1, h2 to t2, and h3 to null.
Lines 14 - 22 find t1 and t2.
Lines 23 - 31 find h2 and h3.
Note that if m is 1, then the first part is empty.
Lines 14 - 22 find t1 and t2.
Lines 23 - 31 find h2 and h3.
Note that if m is 1, then the first part is empty.
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 | /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (head == null || head.next == null) { return head; } ListNode p = head; ListNode t1 = null; int cnt = 1; while (cnt != m) { t1 = p; p = p.next; cnt++; } ListNode t2 = p; ListNode h2 = p; ListNode h3 = p.next; while (cnt != n) { p = h3; h3 = h3.next; p.next = h2; h2 = p; cnt++; } t2.next = h3; if (m == 1) { return h2; } else { t1.next = h2; return head; } } } |
No comments:
Post a Comment