同系列文章导读:【数据结构与算法】导读

所有文章均在本博客首发,其他平台同步更新

如果有更好的方法,欢迎指点,共同进步~~

有其他语言代码也可在留言区留言,谢谢

发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】


  • 时间:2022-05-16
  • 题目序号:24
  • 难度:中等

问题描述

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

来源:力扣(LeetCode)

示例1

img

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

示例2

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

示例3

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

提示

  • 链表中节点的数目在范围 [0, 100]
  • 0 <= Node.val <= 100

解题思路

题解部分参考自LeetCode题解。如有侵权,请联系进行删除~~
  • 本题主要就是模拟链表中结点交换的过程
  • 由题目示例可知,我们需要对链表中无结点、只有一个结点同样做出处理

img

  • 可以加入虚拟头结点来简化操作(不加虚拟头结点需对头结点单独处理,因为没有前一个结点指向头结点)

img

创建虚拟头结点后,还需要3个指针来辅助完成交换操作
  • p结点指向需要交换的两个结点的前一个结点
  • a每次为需要交换的第一个结点,b为需要交换的第二个结点
  • 首先让p.next = b
  • 再让a.next = b.next
  • 最后让b.next = a即可
注意:交换顺序不能乱,否则会断开某些结点之间的连接,可以配合上图理解一下

img

  • 当每次交换完成之后,将p结点指向a结点(下次需要交换的两个结点的前一个位置)

代码实现

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dum = new ListNode(-1);
        dum.next = head;      // 设置虚拟头结点
        ListNode p = dum;
        while(p.next != null && p.next.next != null){     // 链表为空或者只有一个结点时不作处理
            ListNode a = p.next;
            ListNode b = a.next;
            p.next = b;
            a.next = b.next;
            b.next = a;
            p = a;
        }
        return dum.next;
    }
}

在这里插入图片描述

总结

  • 涉及到链表指针的操作时,需要注意顺序问题
  • 顺序不正确的话,可能会导致链表不再连通
  • 使用虚拟头结点可以让首结点由特殊结点转化为一般结点,可以简化问题

END

本文作者: 文章标题:【每日一题】两两交换链表中的节点
本文地址:https://www.hellocode.top/archives/104/
版权说明:若无注明,本文皆HelloCode原创,转载请保留文章出处。
最后修改:2022 年 05 月 16 日
如果觉得我的文章对你有用,请随意赞赏