Skip to content

Latest commit

 

History

History
93 lines (82 loc) · 2.75 KB

24. 两两交换链表中的节点.md

File metadata and controls

93 lines (82 loc) · 2.75 KB
Raw
date created date modified
2022-08-24, 22:07:13
2022-08-24, 22:07:16

Meta

![[CleanShot 2022-09-06 at [email protected]]]

迭代一开始没想出来，最初思维过程如下，可以看到代码很丑陋：

Class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        // 返回第二个节点
        ListNode result = head.next;
        ListNode p = head;
        ListNode prev;
        while (p != null && p.next != null) {
            ListNode temp = p.next;
            p.next = temp.next;
            temp.next = p;
            prev = p; // 从这里其实体现了，需要一个指针用于接收两两翻转后的子链表的新头结点
            p = p.next;
            if (prev.next != null) {
                if (prev.next.next != null) {
                    prev.next = prev.next.next;
                }
            }
        }
        return result;
    }
}

查看题解后：

  1. 添加 dummy 节点
  2. 指针 prev 指向 dummy 节点，指针 p 指向 head 节点
  3. 循环模式变为：prev -> node1 -> node2 交换 node1 和 node2 的位置
Class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode p = head;
        while (p != null && p.next != null) {
            // prev -> node1(p) -> node2(p.next) 交换 node1 和 node2
            ListNode node1 = p;
            ListNode node2 = p.next;
            prev.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            prev = p;
            p = p.next;
        }
        return dummy.next;
    }
}

从上可知：初始指针 p 指向的位置很关键，会影响后续代码的循环逻辑。若指向 head 节点逻辑不是很清晰时，可以考虑指向前一个节点位置（添加 dummy 节点即可），再重新思考逻辑是否更简单。

Class Solution {
    // 递归：给一个链表的头结点，两两交换后返回新头结点
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 剩余节点数大于 2
        ListNode node = swapPairs(head.next.next);
        ListNode newHead = head.next;
        newHead.next = head;
        head.next = node;
        return newHead;
    }
    // 什么时候能用递归？本质上也是找循环模式
    // 关键在于：1 递归出口 2 递推传参 3 循环模式写在前序位置还是后序位置
}