数据结构与算法（两两交换链表中的结点）

原题

24. 两两交换链表中的节点 - 力扣（LeetCode）

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

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

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

解答

建立一个虚拟结点virtual指向head，cur=virtual（让cur始终位于要交换的两个结点的前一个结点），while循环的终止条件：以cur的视角向后看，若链表的大小为偶数，那么要交换的两个结点不能为空，如果链表的大小为奇数，则要交换的两个结点将会有一个为空，此时不需要交换结点，因为cur在最开始就等于vitual，一定不为空，所以无需判断cur是否为空。

以1-2-3-4为例，因为1，2交换后下两个要交换的结点是3，4，所以cur需要在2的位置（在两个要交换的结点前一个位置），当cur到2的位置的时候，cur指向1的链接断开，此时无法获取到结点1，同理，当2要指向1的时候（交换），2指向3的链接也会断开，所以需要用temp1和temp2把这两个结点（1，3）存储起来，交换位置完成后的链表为virtual-2-1-3-4，此时移动cur的位置就是cur=cur.next.next

/*** 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 temp1;ListNode temp2;ListNode virtual=new ListNode();virtual.next=head;ListNode cur=virtual;while(cur.next!=null && cur.next.next!=null){temp1=cur.next;temp2=cur.next.next.next;cur.next=cur.next.next;cur.next.next=temp1;temp1.next=temp2;cur=cur.next.next;}return virtual.next;}
}