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.Note 2: Usually the version often seen in the interviews is reversing the whole linked list which is obviously an easier version of this question
Method:
As we traverse the list, we keep track of the key nodes, and connect them with each other.
Solution:
Time: O(n) Space: o(1)
/** * Definition for singly-linked list. * class ListNode { * public int val; * public ListNode next; * ListNode(int x) { val = x; next = null; } * } */ public class Solution { // 2 4 // 1->2->3->4->5->NULL // p l m // 1->2<-3<-4->5->NULL // 1->4->3->2->5->NULL public ListNode reverseBetween(ListNode A, int B, int C) { ListNode dummy = new ListNode(0); dummy.next = A; ListNode p = dummy; ListNode curr = A; int n = 1; while (n < B && curr != null) { p = curr; curr = curr.next; n ++; } ListNode l = curr; ListNode prev = null; while (n <= C && curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; n ++; } ListNode m = prev; p.next = m; l.next = curr; return dummy.next; } }