leetcode题解24：两两交换链表中的节点

描述

该题来自于力扣第24题

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例1：

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

示例2：

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

示例3：

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

提示：

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

分析

假设当前节点curr以及两个相邻的节点指针first, second，其中curr->first->second，想要交换两个节点，只需要执行以下两步：
1. first->next = second->next
2. second->next = first

此时链表为(curr,second)->first，需再执行一步curr.next = second，链表才会变成curr->second->first

另外就是需要注意几种特殊情况：
1. 对于头部而言，如果first = head，那么curr就不存在，这时只需要设计一个fakeHead指针指向head即可
2. 如果first==null或者second==null，直接结束就可以，因为已经不需要交换了

算法

1. 初始一个fakeHead节点，使其指向链表头部head
2. 令curr = fakeHead
3. 进入循环，循环终止条件为curr.next == null或者curr.next.next == null
4. 令first = curr.next，second = first.next
5. 交换节点first->next = second->next，second->next = first，curr.next = second
6. 更新curr = first，并回到循环初始即步骤3
7. 循环退出，返回新的链表头节点fakeHead.next，程序结束

代码

python3

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        fakeHead = ListNode(0, head)
        curr = fakeHead
        while curr.next and curr.next.next:
            first = curr.next
            second = first.next
            first.next = second.next
            second.next = first
            curr.next = second
            curr = first
        return fakeHead.next

c++

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* fakeHead = new ListNode(0, head);
        ListNode* curr = fakeHead;
        while ((curr->next != NULL) && (curr->next->next != NULL)) {
            ListNode* first = curr->next;
            ListNode* second = first->next;
            first->next = second->next;
            second->next = first;
            curr->next = second;
            curr = first;
        }
        return fakeHead->next;
    }
};

java

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 fakeHead = new ListNode(0, head);
        ListNode curr = fakeHead;
        while ((curr.next != null) && (curr.next.next != null)) {
            ListNode first = curr.next;
            ListNode second = first.next;
            first.next = second.next;
            second.next = first;
            curr.next = second;
            curr = first;
        }
        return fakeHead.next;
    }
}