Reverse A Linked List

Mark as Completed

Lesson

Given a linked list with elements connected by pointers, write a function to reverse the order of the elements in the linked list. The input will be the head of the linked list, and the output should be the new head of the reversed list.

Example input:

1 -> 2 -> 3 -> 4 -> null

Expected output:

4 -> 3 -> 2 -> 1 -> null

Walkthrough

Solution Code:

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function reverseList(head) {
  let previous = null;
  let current = head;

  while (current !== null) {
    let temp = current.next;
    current.next = previous;
    previous = current;
    current = temp;
  }

  return previous;
}

Explanation:

To reverse a linked list, we need to change the pointers of each node to point to the previous node instead of the next node. We start at the head of the list and iterate through each node, updating its next pointer to the previous node. We also need to keep track of the previous and current nodes as we iterate.

In the reverseList
function, we set previous
to null and current
to the head of the linked list. We then loop through the list using a while
loop, which runs until we reach the end of the list (i.e., current
is null
).Inside the loop, we set temp
to the next node of the current
node. We then update the current
node's next pointer to point to previous
, which reverses the pointer. We then update previous
to be the current
node and current
to be the temp
node, which moves us to the next node in the list.Finally, we return previous
, which is the new head of the reversed linked list.

Big O Complexity Analysis:

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. This is because we iterate through the entire list once, updating each node's pointer.

The space complexity is O(1), as we only use a constant amount of extra space to store the previous
, current
, and temp
variables.

Previous Lesson Next Lesson