Sunday, May 3, 2015

[LeetCode] Reverse Linked List II

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->NULLm = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given mn 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.
 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