Leetcode-206. Reverse Linked List

subject

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

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: []

Constraints:

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

solution

Method 1 ： iteration

Suppose the linked list is 1→2→3→∅, We want to change it to ∅←1←2←3.

When traversing a linked list , Set the... Of the current node next The pointer changes to point to the previous node . Because the node does not refer to its previous node , So you have to store its previous node in advance . Before changing the reference , You also need to store the latter node . Finally, the new header reference is returned .

Code

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
    
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Complexity analysis

Time complexity ：O(n), among nn It's the length of the list . You need to traverse the linked list once .
Spatial complexity ：O(1).

Method 2 ： recursive

Code

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
/** *  To list 1->2->3->4->5 give an example  * @param head * @return */
    public ListNode reverseList(ListNode head) {
    
        if (head == null || head.next == null) {
    
            /*  Returns the current node until the next node of the current node is empty   because 5 There is no next node , So the node is returned here 5 */
            return head;
        }
        // Recursively pass in the next node , The purpose is to reach the last node 
        ListNode newHead = reverseList(head.next);
                /*  The first round of stack ,head by 5,head.next It's empty , return 5  The second round of stack ,head by 4,head.next by 5, perform head.next.next=head That is to say 5.next=4,  Point the child nodes of the child nodes of the current node to the current node   At this time, the linked list is 1->2->3->4<->5, because 4 And 5 Point to each other , So disconnect here 4.next=null  At this time, the linked list is 1->2->3->4<-5  Return to node 5  The third round of stack ,head by 3,head.next by 4, perform head.next.next=head That is to say 4.next=3,  At this time, the linked list is 1->2->3<->4<-5, because 3 And 4 Point to each other , So disconnect here 3.next=null  At this time, the linked list is 1->2->3<-4<-5  Return to node 5  The fourth round of stack ,head by 2,head.next by 3, perform head.next.next=head That is to say 3.next=2,  At this time, the linked list is 1->2<->3<-4<-5, because 2 And 3 Point to each other , So disconnect here 2.next=null  At this time, the linked list is 1->2<-3<-4<-5  Return to node 5  The fifth round comes out of the stack ,head by 1,head.next by 2, perform head.next.next=head That is to say 2.next=1,  At this time, the linked list is 1<->2<-3<-4<-5, because 1 And 2 Point to each other , So disconnect here 1.next=null  At this time, the linked list is 1<-2<-3<-4<-5  Return to node 5  Stack out complete , Final header node 5->4->3->2->1 */
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

Complexity analysis

Time complexity ：O(n), among nn It's the length of the list . You need to reverse each node of the linked list .

Spatial complexity ：O(n), among nn It's the length of the list . The space complexity mainly depends on the stack space of recursive calls , At most nn layer .

source

author ：LeetCode-Solution
link ：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .