Question

LeetCode Link | 206. Reverse Linked List | Easy

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

Constrains

  • The number of nodes in the list is the range [0, 5000].
  • -5000 <= Node.val <= 5000

Example

Example 1

Example 1

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

Example 2

Input: head = [1,2]
Output: [2,1]

Example 3

Input: head = []
Output: []

Solution Approach

Method: Two-pointers

Constrains

  • None

This method does not have any limitations.

Concept Explanation

If we define a new linked list to implement the reversal of the elements, it actually wastes memory space. In fact, it only need to change the direction of the next pointer in the linked list to revserse it directly without having to redefine a new linked list, as shown in the figure below:

Revserse Linked List

First, define a cur pointer that points to the head node, and then define a pre pointer, initialize to null.

init pointers

Now, start the reversal process. First, save the cur.next node with a tmp pointer. Why save this node? Because you need to change the direction of cur.next which wil lost its current direction.

We can now set cur.next to point to pre, at this point, the first node has been reversed. Next, continue with the following code logic in a loop, moving the pre and cur pointers. [pre->cur & cur->tmp]

reverse one node

We will do the same step with the next following nodes.

reverse one node continue

Finally, the cur pointer will point to null, the loop ends, and the linked list reversal is complete. At this point, returning the pre pointer is sufficient, as pre now points to the new head node.

return new head node

Code

  • Time complexity: O(n)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
    let preNode: ListNode | null = null,
        curNode: ListNode | null = head,
        tempNode: ListNode | null;
    while (curNode) {
        tempNode = curNode.next;
        curNode.next = preNode;
        preNode = curNode;
        curNode = tempNode;
    }
    return preNode;
};

Conclusion

This question helps solidify one’s understanding of linked lists, a basic data structure used in many computing applications. It requires manipulating node pointers, which is a crucial aspect of working with linked lists.