Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
YouTube
Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, m = 2, n = 4
Output: 1 -> 4 -> 3 -> 2 -> 5 -> NULL
Reverse even elements in a Linked List - GFG
Last updated
Was this helpful?
Was this helpful?
// Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}/**
* Time complexity : O(N) considering the list consists of N nodes.
* We process each of the nodes at most once (we don't process the nodes
* after the nth node from the beginning).
* Space complexity : O(1) since we simply adjust some pointers in the
* original linked list and only use O(1) additional memory for achieving
* the final result.
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null || m > n) return head;
ListNode curr = head;
ListNode first = head, last = null;
ListNode bfr = null, aft = null;
int i = 1;
while(i < m) {
bfr = curr;
curr = curr.next;
i++;
}
first = curr;
while(i <= n) {
ListNode temp = curr.next;
curr.next = last;
last = curr;
curr = temp;
i++;
}
aft = curr;
// Input: head -> .. -> bfr -> reverse(first -> .. -> last) -> aft
// Output: head -> .. -> bfr -> last -> .. -> first -> aft
if(bfr == null && aft == null) {
return last;
}
if(bfr == null) {
first.next = aft;
return last;
}
if(aft == null) {
bfr.next = last;
return head;
}
bfr.next = last;
first.next = aft;
return head;
}
}