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

末蓝、 2024-03-17 20:40 41阅读 0赞

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

*  题干背景
 *  重要思路
 *  代码实现

## 题干背景 ##

[力扣入口-24. 两两交换链表中的节点][-24.]

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

![在这里插入图片描述][140bf64aa87349329b3f7f08c0477335.png]

## 重要思路 ##

1.  仍然使用虚拟头结点，否则很麻烦。
2.  画图来模拟一次交换相邻元素的过程：  
    ![在这里插入图片描述][7f8b40693203427ba7e078a19804cfc9.png]
3.  注意可以使用两个节点来保存之前的节点信息（一组中的1和2节点），代码中使用的是firstnode和secondnode。另外，使用temp节点来保存节点3的信息。
4.  终止条件中注意两个条件的放置位置，必须这样放置。这两个终止条件其实是对应于偶数个元素的链表和奇数个元素的链表。
5.  可以拓展使用迭代法来解决。

## 代码实现 ##

// 24. 两两交换链表中的节点
    public ListNode swapPairs(ListNode head){
        
        ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头节点
        dumyhead.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode cur = dumyhead;
        ListNode temp; // 临时节点，保存两个节点后面的节点
        ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
        ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
        while(cur.next != null && cur.next.next != null){
        
            temp = cur.next.next.next;
            firstnode = cur.next;
            secondnode = cur.next.next;
            cur.next = secondnode; // 步骤一
            secondnode.next = firstnode; // 步骤二
            firstnode.next = temp; // 步骤三
            cur = firstnode; // cur移动，准备下一轮交换
        }
        return dumyhead.next;
    }

**参考资料**：[24. 两两交换链表中的节点][24.]

[-24.]: https://leetcode.cn/problems/swap-nodes-in-pairs/description/
[140bf64aa87349329b3f7f08c0477335.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/3a4e13b8d6aa4ab6b5eb319e68b00115.png
[7f8b40693203427ba7e078a19804cfc9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/96c23d082bd24d74b329a7788d235cb7.png
[24.]: https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC