leetcode.24.两两交换链表中的节点(swap-nodes-in-pairs)

以你之姓@ 2022-12-14 03:57 173阅读 0赞

# 两两交换链表中的节点(swap-nodes-in-pairs) #

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes. Only nodes itself may be changed.

**Example 1:**  
![在这里插入图片描述][e08457f793564160de44f1fd1b6d34ac.png_pic_center]

Input: head = [1,2,3,4]
    Output: [2,1,4,3]

**Example 2:**

Input: head = []
    Output: []

**Example 3:**

Input: head = [1]
    Output: [1]

# 代码与思路 #

## 迭代 ##

[来自——两两交换链表中的节点(swap-nodes-in-pairs)官方][swap-nodes-in-pairs]  
![在这里插入图片描述][20201013103717888.png]  
这里定义了一个哑节点，获取了node1，node2，交换它们，`temp`指针再向前走就可以了。注意，**终止条件**是 `temp`的后面没有节点或者只有一个节点，则没有更多的节点需要交换，因此结束交换。迭代的话，想清楚，终止条件是什么非常关键。

class Solution { 
    public:
        ListNode* swapPairs(ListNode* head) { 
        	//定义一个哑节点
            ListNode* dummyHead = new ListNode(0);
            dummyHead->next = head;
            ListNode* temp = dummyHead;
            while (temp->next != nullptr && temp->next->next != nullptr) { 
            	//准备待交换的节点
                ListNode* node1 = temp->next;
                ListNode* node2 = temp->next->next;
                //交换
                temp->next = node2;
                node1->next = node2->next;
                node2->next = node1;
                //移动指针
                temp = node1;
            }
            //返回
            return dummyHead->next;
        }
    };

## 递归(有点难度) ##

public ListNode swapPairs(ListNode head) { 
            //边界条件判断
            if (head == null || head.next == null)
                return head;
            //从第3个链表往后进行交换
            ListNode third = swapPairs(head.next.next);
            //从第3个链表往后都交换完了，我们只需要交换前两个链表即可,
            //这里我们把链表分为3组，分别是第1个节点，第2个节点，后面
            //的所有节点，也就是1 → 2 → 3，我们要把它变为2 → 1 → 3
            ListNode second = head.next;
            head.next = third;			//你可能会觉得，这里不是指向1吗
            second.next = head;
            
            return second;
        }

说明 `head.next = third;`你可能会觉得奇怪，这里不是指向`1`那个节点吗，为什么是指向`3`，注意了，这里跟迭代的方式有点不一样，我们返回的是一个新的头结点，它叫`second`。所以，我们用`second`来连接后面的节点，你也可以调整一下代码格式，这样子看。

head.next = third;
            second.next = head;

也就是说`second -> head -> third`。

[来自sdwwld][sdwwld]

# 其它 #

ListNode 的定义

Definition for singly-linked list.
      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) {}
      };

[e08457f793564160de44f1fd1b6d34ac.png_pic_center]: /images/20221123/055dcb5e853f4437b6197a6f9cf29662.png
[swap-nodes-in-pairs]: https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91/
[20201013103717888.png]: /images/20221123/80d52067b69940c7b467eef480c8971d.png
[sdwwld]: https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/di-gui-he-fei-di-gui-liang-chong-fang-shi-jie-ju-2/