LeetCode | 24 两两交换链表中的节点

题目

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

示例

给定 1->2->3->4，返回 2->1->4->3。

说明：

• 算法只能使用常数的额外空间；
• 不能只是单纯的交换节点内部的值，而是需要实际的进行节点交换。

题解

这个题目非常并不难，简单叙述下思路如下：

1. 链表为空或只有一个节点时时直接返回头节点；
2. p1 指向第一个节点，p2 指向第二个节点，进行交换；交换之后 p2 成为头节点，更新头节点；p1 指向第二个节点；
3. 现在 p1 成为第二个 pair 的头节点；
4. 当 p1->next和 p1->next->next 不为空时执行：
   • 交换 p1->next和 p1->next->next
   • p1 = p1->next->next

代码如下：

LeetCodeSolution24.cview raw

// 链表节点定义
typedef struct ListNode{
    int val;
    struct ListNode *next;
} ListNode;

ListNode *swapPairs(ListNode *head)
{
    if (head == NULL || head->next == NULL)
        return head;
    ListNode *p1, *p2;
    p1 = head;
    p2 = p1->next;
    // 第一次交换
    p1->next = p2->next;
    p2->next = p1;
    head = p2;
    // 其他
    while (p1->next && p1->next->next)
    {
        exch(p1, p1->next);
        p1 = p1->next->next;
    }
    return head;
}

void exch(ListNode *p1, ListNode *p2)
{
    p1->next = p2->next;
    p2->next = p2->next->next;
    p1->next->next = p2;
}