[Algorithm] 5. Linked list in-place Reversal

Linked list in-place Reversal

Reverse Linked List (LeetCode #206)

In most cases, the pure iterative algorithm is preferred as it provides the best real-world performance (no bloated call stacks) while keeping the function pure. Pure functions are preferred in many cases, especially when there may be multiple algorithms running in parallel on the same list.

In cases where parameter ownership is known, the impure iterative algorithm is prefferred as it provides the best time and space complexity in the tight case. Keep in mind that the TypeScript compiler cannot determine parameter ownership at compile time, so new code may break this constraint. Short of rewriting your solution in Rust, documentation is the best remedy for this.

/**
 * Definition for singly-linked list.
 *
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

Pure Iterative

function reverseList(head: ListNode | null): ListNode | null{
	let newLinked : ListNode | null = null;
	
	while(head){
		newLinked = new ListNode(head.val, newLinked); 
		head = head.next; 
	}
	
    return newLinked; 
}

Impure Iterative

function reverseList(head: ListNode | null): ListNode | null{
let newLinked = null;

	while(head) {
      	let next = head.next; 
        head.next = newLinked;
        newLinked = head;
     	head = next;
 	 }

	return newLinked;	 
}

Pure Recursive

function reverseList(head: ListNode | null): ListNode | null{
	if(!head) return head; 
	function reverse(curr: ListNode, parent: ListNode | null) : ListNode{
		const next = curr.next; 
		curr = new ListNode(curr.val, parent); 
		if(!next) return curr; 
		return reverse(next, curr);
	}

	return reverse(head, null);
}

Impure Recursive

function reverseList(head: ListNode | null, parent?: ListNode | null): ListNode | null{
	if(!head) return parent || null; 
	const next = head.next; 
    head.next = parent || null; 
	
    return reverseList(next, head) 
}

Reverse Linked List II (LeetCode #92)

function reverseBetween(
  head: ListNode | null,
  left: number,
  right: number
): ListNode | null {
  let dummy = new ListNode(0, head);

  let beforeLeft: ListNode | null = dummy;

  let curr = head;

  for (let i = 1; i < left; i++) {
    beforeLeft = curr;
    curr = curr?.next || null;
  }

  let sublistTail = curr!;
  let prev: ListNode | null = null;

  for (let i = left; i <= right; i++) {
    const nextNode = curr?.next || null;
    curr!.next = prev;
    prev = curr;
    curr = nextNode;
  }

  beforeLeft!.next = prev;
  sublistTail.next = curr;

  return head;
}

Without dummy node

  let leftNodeTail: ListNode | null = null;
  let curr = head;
  for (let i = 1; i < left; i++) {
    leftNodeTail = curr;
    curr = curr?.next || null;
  }

  // 2, 3, 4 => 4 , 3 , 2
  // 2 is tail
  let sublistTail = curr!;
  let reversed: ListNode | null = null;

  for (let i = left; i <= right; i++) {
    const nextNode = curr?.next || null;
    curr!.next = reversed;
    reversed = curr;
    curr = nextNode;
  }

  sublistTail.next = curr;
  if (leftNodeTail) {
    leftNodeTail.next = reversed;
  } else {
    // equals to left 1, entire node reversed
    head = reversed;
  }

  return head;

Swap Nodes in Pairs (LeetCode #24)

My code

function swapPairsMine(head: ListNode | null): ListNode | null {
  if (!head?.next) return head;

  const startNode = head?.next;
  let curr: ListNode | null = head,
    prevTail: ListNode | null = null;

  while (curr?.next) {
    const nextPairStart: ListNode | null = curr.next.next;
    const pairHead = curr.next;
    const pairTail = curr;

    prevTail && (prevTail.next = pairHead);

    pairHead.next = pairTail;
    pairTail.next = nextPairStart;

    prevTail = pairTail;
    curr = nextPairStart;
  }

  return startNode;
}

slution 1

function swapPairs(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;
  let dummy = new ListNode(0, head);

  let prev = dummy;
  let slow: ListNode | null = head;
  let fast: ListNode | null = head.next;

  while (slow && fast) {
    prev.next = fast;
    slow.next = fast.next;
    fast.next = slow;

    prev = slow;
    slow = slow.next || null;
    fast = slow?.next || null;
  }

  return dummy.next;
}

slution 2

let newHead: ListNode | null = null;

  let prev: ListNode | null = null;
  let slow = head;
  while (slow && slow.next) {
    let fast: ListNode | null = slow.next.next;
    let temp: ListNode | null = slow.next;

    slow.next = fast;
    if (temp) {
      temp.next = slow;
    }

    if (prev) {
      (prev as ListNode).next = temp;
    } else {
      newHead = temp;
    }

    prev = slow;
    slow = fast;
  }
  return newHead;