In-Place Reversal

This technique reverse the links between a set of nodes of a linked list using the existing node objects and without using extra memory.

How to Identify

• Data Structure Involves: Linked List
• Question Type: If the problem requires reversing a linked list without using extra memory.

Example

Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Recursive

reverseLinkedList.ts

import {ListNode} from "./ListNode"
function reverseList(head: ListNode | null): ListNode | null {
    return reverse(null, head)
}
function reverse(previous: ListNode | null, current: ListNode | null): ListNode | null{
    // base case
    if(current == null) return previous
    
    // recursive case
    const next = current.next
    current.next = previous
    
    return reverse(current, next)
}

Iterative

reverseList.ts

import {ListNode} from "./ListNode"
function reverseList(head: ListNode | null): ListNode | null {
    return reverse(null, head)
};
function reverseListIterative(head: ListNode | null): ListNode | null {
    let previous: ListNode | null = null, next: ListNode | null
    
    while(head)  {
        next = head.next
        head.next = previous
        previous = head
        head = next
    }
    return previous
}

ListNode

ListNode.ts

export 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)
  }
}

Related Problems

	Problems	Difficulty
1	Reverse Linked List	Easy
2	Swap Nodes in Pairs	Medium
3	Reverse Nodes in k-Group	Hard