Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->->->2->1->NULL
Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Reversing a linked list (an the data structure of a linked list itself) is not an essential technique you would need to master during your daily work life. However, it is a quite popular interview question (being asked in candidate screenings)

Generally speaking, to reverse a linked list, you can do this in recursion or iteratively.

Recursively Reverse a Linked List

To solve this problem recursively, we have to think recursively. First, we can split the linked list into two halves. The nodes that have been reversed and the remaining linked list that are yet to reverse.

Then, for current node, we have to reverse its directions, by reverse pointing its next node (to itself) and point current node to NULL (delete the original link).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (!head) return null;
    if (!head.next) return head;
    let rev = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return rev;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (!head) return null;
    if (!head.next) return head;
    let rev = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return rev;
};

Iteratively Reverting a Linked List

By iteration, the algorithm to reverse a linked list is much easier to understand. We need to maintain a previous node (which is set to NULL at the beginning). Then, as we move forwards along the linked list, we point current node’s direction to the previous node, then we move one node until the end (updating the previous node, current node).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let prev = null;
    while (head) {
        let p = head.next;
        head.next = prev;
        prev = head;
        head = p;        
    }
    return prev;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let prev = null;
    while (head) {
        let p = head.next;
        head.next = prev;
        prev = head;
        head = p;        
    }
    return prev;
};

To Reverse a linked list using Top-Bottom Recursion, Bottom-Up Recursion or Iterative Approach in C++, you can refer to this post: How to Reverse a Linked List in C/C++?

–EOF (The Ultimate Computing & Technology Blog) —