206. Reverse Linked List.md

206. Reverse Linked List

1. Description

Reverse a singly linked list.

Example:

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

Follow up:

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

2. Solutions

Solution 1: Language: C Iteration Solution

This problem could be solved iteratively by three pointers: prev, curr and succ. Update the next pointer for every node in the linked list, and then return the new head prev pointer. Refer to the diagram below.

• Sunday, 18 October, 2020
• Time Complexity: $O(n)$
• Space Complexity: $O(1)$
• Runtime: 4 ms, faster than 77.81% of C online submissions for Reverse Linked List.
• Memory Usage: 6.5 MB, less than 16.75% of C online submissions for Reverse Linked List.

/*
Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};
*/

// Use 3 pointers to update the linked list.
// Refer to the diagram.
struct ListNode *reverseList(struct ListNode *head) {
    struct ListNode *prev = NULL;
    struct ListNode *curr = head;
    struct ListNode *succ = NULL;
    while (curr != NULL) {
        succ = curr->next;
        curr->next = prev;
        prev = curr;
        curr = succ;
    }
    // Now the pointer `prev` is the new head.
    return prev;
}