92. Reverse Linked List II

Description

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, m = 2, n = 4

Output: 1 -> 4 -> 3 -> 2 -> 5 -> NULL

Solutions

ListNode

// 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;
	}
}

Solution 1

/**
 * 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;
    }
}

Follow up

• Reverse even elements in a Linked List - GFG