[LeetCode] 92. 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->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.

Thought process:

Say left = node before m and right = node after n, mNode = node at m and nNode = node at n. The idea is to find these four nodes, reverse the list between mNode and nNode based on "206. Reverse Linked List", and connect left to nNode and mNode to right.

Solution:

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 41

/** * 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) { ListNode dummy = new ListNode(0); dummy.next = head; int index = 0; ListNode current = dummy; for (; index + 1 < m; index++) { current = current.next; } ListNode left = current; ListNode previous = null; current = current.next; ListNode mNode = current; index++; for (; index <= n; index++) { ListNode next = current.next; current.next = previous; previous = current; current = next; } ListNode right = current; left.next = previous; mNode.next = right; return dummy.next; } }

Time complexity: O(n).