Source: LeetCode

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

Example 1:

Enter: head = [1.2.3.4.5] output: [5.4.3.2.1]
Copy the code

Example 2:

Enter: head = [1.2] output: [2.1]
Copy the code

Example 3:

Input: head = [] Output: []Copy the code

Tip:

  • The number of nodes in the list ranges from 0 to 5000.
  • -5000 <= Node.val <= 5000

Method 1: iteration

var reverseList = function(head) {
    let cur = head;
    let pre = null;
    while (cur) {
        let temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp
    }
    return pre;
};
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(1)O(1).

Method two: recursion

If you want to reverse nodes 1 and 2, you can do this:

head.next.next = head;
head.next = null;   / / 1 < = 2
Copy the code

We recurse by using this idea over and over again:

reverseList: head=1
    reverseList: head=2
	    reverseList: head=3
		    reverseList:head=4
			    reverseList:head=5Terminating returns cur =5

			4.next.next->4, i.e.,5->4
            cur = 5 -> 4 -> null

        3.next.next->3, i.e.,4->3
        cur = 5 -> 4 -> 3 -> null

    2.next.next->2, i.e.,3->2
    cur = 5 -> 4 -> 3 -> 2 -> null
	
1.next.next->1, i.e.,2->1
cur = 5 -> 4 -> 3 -> 2 -> 1 -> null
Copy the code

Look at the code:

var reverseList = function(head) {
    if (head == null || head.next == null) {
        return head;
    };
    let newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
};
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(n)