Theory

In-place linkedlist reversal theory

I/P: head -> 2 -> 4 -> 6 -> 8 -> 10 -> null

     2 -> 4

previous = null
current = 2

#1
temp = 2.next = 4
2.next = previous = null
previous = current = 2
current = temp = 4

state after first iteration: null <- 2  4

#2
temp = null
4.next = previous = 2
previous = current = 4
current = temp = null

state: null <- 2 <- 4

terminating condition: current == null

-----

2 -> 4 -> 6

previous = null
current = 2

#1
temp = current.next = 4
current.next = previous
previous = current
current = temp

state: null <- 2 4 -> 6

#2
temp = current.next = 6
current.next = previous = 2
previous = current
current = temp

state: null <- 2 <- 4 6

#3
temp = current.next = null
current.next = previous = 4
previous = current = 6
current = temp = null

O/P: head -> 10 -> 8 -> 6 -> 4 -> 2 -> null

Video

Questions

Given the head of a Singly LinkedList, reverse the LinkedList. Write a function to return the new head of the reversed LinkedList.

I/P: head -> 2 -> 4 -> 6 -> 8 -> 10 -> null

O/P: head -> 10 -> 8 -> 6 -> 4 -> 2 -> null

Implementation: [ReverseInPlace][ReverseInPlace.java]

Explanation in theory.

Time complexity

O(n)

Space complexity

O(1)

Return to Index