[编程题] lc 24 两两交换链表中的节点

[编程题] lc:24. 两两交换链表中的节点

题目描述

输入输出例子

思路

参考：https://www.bilibili.com/video/BV1VC4y1s75E?from=search&seid=7587439253853836582

先构造一个dummy节点，指向和连接这个链表。再使用这三个指针进行。

while的退出条件对于奇数偶数的链表都是：

pre.next!=null && pre.next.next!=null （y也就是说，当pre.next的指向和pre.next.next的指向都不能悬空才指向while循环。）

方法1：三个指针

时间复杂度：O（n）  空间复杂度：O（n）

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        //1 先构造一个dummy节点，并连接成链表
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        pre.next = head;

        //2 循环解决
        while(pre.next!=null && pre.next.next!=null){
            ListNode cur = pre.next;
            ListNode next = pre.next.next;

            //三个指向关系
            pre.next = cur.next;
            cur.next = next.next;
            next.next = cur;

            //pre指针往前移动
            pre = pre.next.next;
        }

        //返回信息
        return dummy.next;

    }
}

输出：