当前位置：首页 > article >正文

算法4（力扣206）-反转链表

article 2025/1/19 23:53:33

1、问题

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

2、采用例子

输入：head = [1,2]

输出：[2,1]

3、实现思路

改变链表箭头的指向

4、具体步骤

（1）定义链表类

（2）定义头结点

（3）实现函数

1）空链表直接返回

2）非空链表

（这里用123为例）

①创建一个临时变量，用于反转时的最终指向

②创建当前节点指向头结点

③进入循环（当前节点非空时，进入循环）

④存储当前节点的下一节点（否则反转箭头时会丢失）

⑤让当前节点指向临时变量（反转箭头）

⑥反转一个箭头后，当前节点后移（将当前节点的值赋给临时变量，类似于之前常用的cur=cur.next）

⑦临时变量的指针也后移，方便非空时进行下一次反转箭头

⑧循环外，打印并返回新链表

5、完整代码

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>反转链表</title>
</head>
<body>
    <p>
        给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    </p>
    <p>
        输入：head = [1,2]
        输出：[2,1]
    </p>
    <script>
        class ListNode{
            constructor(val,next){
                this.val = val
                this.next = next
            }
        }
        let head = new ListNode(1)
        head.next = new ListNode(2)
        // console.log(head);
        reverseList(head)
        function reverseList(head){
            if(!head) return head;
            //新链表的最后一位（临时变量）
            let pre = null
            let cur = head
            while (cur) {
                // nxt用于存储下一个元素
                nxt = cur.next
                // 反转链表箭头
                cur.next = pre
                // 新链表后移一位（让新链表的最后一位指针指向当前节点的前一位）
                pre = cur
                // 当前节点后移
                cur = nxt
            }  
            console.log(pre);
              
            return pre
        }
    </script>
</body>
</html>

6、力扣通过代码


var reverseList = function(head) {
    if(!head) return head;
            //新链表的最后一位（临时变量）
            let pre = null
            let cur = head
            while (cur) {
                // nxt用于存储下一个元素
                nxt = cur.next
                // 反转链表箭头
                cur.next = pre
                // 新链表后移一位（让新链表的最后一位指针指向当前节点的前一位）
                pre = cur
                // 当前节点后移
                cur = nxt
            }  
            console.log(pre);
              
            return pre
};

查看全文

http://www.kler.cn/a/509930.html