0092. Reverse Linked List II

https://leetcode.com/problems/reverse-linked-list-ii

Description

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

**Input:** head = [1,2,3,4,5], left = 2, right = 4
**Output:** [1,4,3,2,5]

Example 2:

**Input:** head = [5], left = 1, right = 1
**Output:** [5]

Constraints:

• The number of nodes in the list is n.

• 1 <= n <= 500

• -500 <= Node.val <= 500

• 1 <= left <= right <= n

Follow up: Could you do it in one pass?

ac

12/25/2017 when struture change, use dummy node

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // corner cases;
        if (head == null || head.next == null || m == n) return head;

        ListNode n1 = head, n2 = head;
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        prev.next = n1;
        // get to m & n
        int k = 1;
        while (n2.next != null && k < n) {
            n2 = n2.next;
            if (k > n - m) {
                prev = n1;
                n1 = n1.next;
            }
            k++;
        } 
        if (k < n) return head;

        // reverse
        prev.next = n2;
        ListNode p2 = n2.next;
        while (n1 != n2) {
            ListNode tmp = n1;
            n1 = n1.next;
            tmp.next = p2;
            p2 = tmp;
        }
        n1.next = p2;

        return dummy.next;
    }
}