Leetcode 24：Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

说人话：

将链表中元素每两个交换一下。

举例：

[法1] 穿针引线

思路

本题是比较复杂的穿针引线。首先我们需要定义 4 个指针：

• pre：交换结点对的前一个结点
• node1：第一个要交换的结点
• node2：第二个要交换的结点
• next：交换结点对的下一个节点

交换过程如下图：

pre->next = node2

node2.next = node1

node1.next = next;

拉直后：

交换后继续往后交换：

p = node1

当没有下一轮需要交换的时候（pre.next == null）就完成了。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {

        //虚拟头结点
        ListNode dummyHead = new ListNode(0,head);
        //前一个节点
        ListNode pre = dummyHead;
        
        //穿针引线
        while(pre.next != null){
            //第一个节点
            ListNode node1 = pre.next;
            if(node1 == null){
                break;
            }
            //第二个节点
            ListNode node2 = node1.next;
            if(node2 == null){
                break;
            }
            //下一结点
            ListNode next = node2.next;
            //交换
            pre.next = node2;
            node2.next = node1;
            node1.next = next;
            pre = node1;
        }

        return dummyHead.next;

    }
}

提交结果

代码分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)