关于javascript:Leetcode反转链表

41次阅读

共计 848 个字符,预计需要花费 3 分钟才能阅读完成。

起源:力扣(LeetCode)

给你单链表的头节点 head,请你反转链表,并返回反转后的链表。

示例 1:

 输出:head = [1,2,3,4,5]
输入:[5,4,3,2,1]

示例 2:

 输出:head = [1,2]
输入:[2,1]

示例 3:

 输出:head = []
输入:[]

提醒:

  • 链表中节点的数目范畴是 [0, 5000]
  • -5000 <= Node.val <= 5000

办法一:迭代

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;
};
  • 工夫复杂度:O(n)
  • 空间复杂度:O(1)O(1)。

办法二:递归

如果要让节点 1 和节点 2 反转的话,能够这样做:

head.next.next = head;
head.next = null;   // 1 <= 2

咱们递归就是一直地利用这种思维:

reverseList: head=1
    reverseList: head=2
        reverseList: head=3
            reverseList:head=4
                reverseList:head=5 
                    终止返回
                cur = 5

            4.next.next->4,即 5 ->4
            cur = 5 -> 4 -> null

        3.next.next->3,即 4 ->3
        cur = 5 -> 4 -> 3 -> null

    2.next.next->2,即 3 ->2
    cur = 5 -> 4 -> 3 -> 2 -> null
    
1.next.next->1,即 2 ->1
cur = 5 -> 4 -> 3 -> 2 -> 1 -> null

请看代码:

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;
};
  • 工夫复杂度:O(n)
  • 空间复杂度:O(n)

正文完
 0