【leetcode】链表-两两交换链表中的节点_交换节点。两两交换其中相邻的节点,不能只改变节点内部的值,而是需要进行指针

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

---

1.思路一：
使用递归的思想
最简化为第一步的操作，也就是head.next=head这个操作
之后在每两个交换之间弄一条next即可

如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

用 head 表示原始链表的头节点，新的链表的第二个节点，用 p 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 p.next。令 head.next = swapPairs(p.next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 p.next = head，即完成了所有节点的交换。最后返回新的链表的头节点 p。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode p=head.next;
        head.next=swapPairs(p.next);
        p.next=head;

        return p;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

2.思路二：
利用迭代的思想，交换的同时需要一个临时变量来存储
此算法也行得通，但在leetcode上超出时间限制

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode prevhead = new ListNode(0);
        prevhead.next = head;
        ListNode prev = prevhead;
        ListNode cur=head;
        ListNode rear=head.next;
        while (cur != null && rear != null) {
            prev.next = rear;
            cur.next = rear.next;
            rear.next = cur;
            prev = cur;
            cur=rear;
            rear=rear.next;
        }
        return prevhead.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

改进上面算法：

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16