跳转至

24. 两两交换链表中的节点

最后更新：2024-05-10-22

链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/

题目描述

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

题目示例

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

输出： [2,1,4,3]

输入： head = []

输出： []

输入： head = [1]

输出： [1]

提示：

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

思路

简单的思路，向将链表拆分成两个list 然后将这两个链表进行合并

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/


#define INSERT_LIST_NEXT(list, node) \
    (list)->next = node;\
    (node) = (node)->next;\
    (list) = (list)->next;

#define INSERT_LIST(list, node) \
    (list)->next = node;\
    (list) = (list)->next;\
    (list)->next = NULL;

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode head = {0,NULL};
    struct ListNode *temp = &head;

    // 遍历，插入
    while ((list1 != NULL) && (list2 != NULL)) {
        INSERT_LIST_NEXT(temp, list1);
        INSERT_LIST_NEXT(temp, list2);
    }

    // 插入l1。L2为空
    while (list1 != NULL) {
        INSERT_LIST_NEXT(temp, list1);
    }

    // 插入l2，l1为空
    while (list2 != NULL) {
        INSERT_LIST_NEXT(temp, list2);
    }

    return head.next;
}

struct ListNode* swapPairs(struct ListNode* head)
{
    if ((head == NULL) || (head->next == NULL)) {
        return head;
    }

    struct ListNode list1 = {0,NULL};
    struct ListNode list2 = {0,NULL};

    // 先拆成两个链表，然后重新合并
    struct ListNode* temp = head;
    struct ListNode* temp1 = &list1;
    struct ListNode* temp2 = &list2;
    int flag = 1;
    while (temp != NULL) {
        struct ListNode* next = temp->next;
        if (flag == 1) {
            INSERT_LIST(temp1, temp);
            flag++;
        } else {
            INSERT_LIST(temp2, temp);
            flag--;
        }
        temp = next;
    }

    return mergeTwoLists(list2.next, list1.next);
}
Go
1