leetcode206.Reverse Linked List

Problem Description

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

Approach

To reverse a linked list, we can iteratively change the direction of the pointers. We initialize three pointers: pre, cur, and tmp.

• pre initially points to null, as it will be the new head of the reversed list.
• cur starts at the original head of the linked list.
• tmp is used to store the next node temporarily while we reverse the direction of the pointers.

We traverse the linked list using a while loop until we reach the end of the list (i.e., cur becomes null). In each iteration, we perform the following steps:

1. Store the next node of cur in tmp. This is necessary because changing the direction of cur.next will disconnect the remaining part of the linked list.
2. Change the direction of cur.next to point to pre, reversing the pointer of the current node.
3. Move pre to cur and cur to tmp for the next iteration.

Finally, we return pre as the new head of the reversed linked list.

Implementation with Comments

public ListNode reverseList(ListNode head) {
    // Initialize three pointers: pre, cur, and tmp
    ListNode pre = null; // pre initially points to null
    ListNode cur = head; // cur starts at the original head of the linked list
    ListNode tmp = null; // tmp is used to store the next node temporarily while we reverse the direction of the pointers

    // Traverse the linked list using a while loop until we reach the end of the list (i.e., cur becomes null)
    while (cur != null) {
        // Store the next node of cur in tmp. This is necessary because changing the direction of cur.next will disconnect the remaining part of the linked list.
        tmp = cur.next;
        // Change the direction of cur.next to point to pre, reversing the pointer of the current node
        cur.next = pre;
        // Move pre to cur and cur to tmp for the next iteration
        pre = cur;
        cur = tmp;
    }
    
    // Return pre as the new head of the reversed linked list
    return pre;
}

Complexity Analysis

• Time complexity: O(n), where n is the length of the linked list. We need to traverse the entire linked list once.
• Space complexity: O(1), using only constant extra space.

By iteratively changing the direction of the pointers, we can reverse the linked list in linear time. The space complexity is constant because we are using only a fixed number of pointers.

This problem showcases a common operation on linked lists. By understanding the concept of reversing a linked list and manipulating the pointers correctly, we can efficiently solve similar problems.

感谢您的来访，获取更多精彩文章请收藏本站。