两两交换链表中的节点

LeetCode 24 · Medium · 1 min · 榎aaaa

使用的是迭代

就像之前写过的大部分链表的题目一样，要创建一个哨兵节点（前置节点）

首先哨兵节点指向第一个节点，之后进入循环，前置节点指向第二个节点，第一个节点指向第三个节点，最后让第二个节点指向原来的第一个节点，将前置节点指向此时的第二个节点，进入下一次循环

 1ListNode* swapPairs(ListNode* head)
 2    {
 3        if( !head || !head->next ) return head;
 4        ListNode header1(0, head);
 5        ListNode* prev = &header1;
 6
 7        while(prev->next && prev->next->next)
 8        {
 9            auto node1 = prev->next;
10            auto node2 = prev->next->next;
11
12            prev->next = node2;
13            node1->next = node2->next;
14            node2->next = node1;
15
16            prev = node1;
17        }
18
19        return header1.next;
20    }

补充解法：递归交换相邻节点

1ListNode* swapPairs(ListNode* head)
2{
3    if(head == nullptr || head->next == nullptr) return head;
4
5    ListNode* newHead = head->next;
6    head->next = swapPairs(newHead->next);
7    newHead->next = head;
8    return newHead;
9}

来源：语雀原笔记