反转链表

曾经终败给现在 2022-12-27 01:21 204阅读 0赞

> [剑指Offer 24 反转链表 \[easy\] ][Offer 24 _ _easy_]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]

### 题解1 ###

1.  思路：栈
2.  时间复杂度：O(n) O(2 \* n) 入栈 + 出栈
3.  空间复杂度：O(n) 栈空间
4.  实现
    
        /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
        /** * @param {ListNode} head * @return {ListNode} */
        var reverseList = function(head) { 
            // 预处理
            if(!head) return head;
            
            let stack = [head];
            let curr = head;
            while(curr.next){ 
                stack.push(curr = curr.next);
            }
            let result = stack.pop();
            while(curr.next = stack.pop() || null) curr = curr.next;
            return result;
        };

### 题解2 ###

1.  思路：双引用(指针)法 pre, curr
2.  时间复杂度：O(n)
3.  空间复杂度：O(1) 指针空间
4.  实现
    
        /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
        /** * @param {ListNode} head * @return {ListNode} */
        var reverseList = function(head) { 
            // 预处理
            if(!head) return head;
        	
        	// 双引用法
            let pre = head;
            let curr = pre.next;
            pre.next = null;	// 反转链表尾指向null
            while(curr){ 
                let temp = curr;
                curr = curr.next;
                temp.next = pre;
                pre = temp;
            }
            return pre;
        };

[Offer 24 _ _easy_]: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]: /images/20221120/cc778d9bc6a9478ea6f40953b3634d4b.png