24. Swap Nodes in Pairs[M]两两交换链表中的节点

快来打我* 2021-11-23 07:06 157阅读 0赞

# 题目 #

--------------------

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:**  
 Given 1->2->3->4，you should return the list as 2->1->4->3.

# 思路 #

--------------------

### 思路一：遍历交换 ###

本题需要我们对链表进行两两的交换，并且  
**1.如何交换表头**  
这里已经用过很多遍了，在链表的表头增加一个辅助节点。

ListNode* result = new ListNode(-1);
    result->next = head;

**2.如何进行链表的两两交换**  
链表的交换涉及到三个节点：当前节点（cur），当前节点的下一个节点（first），当前节点的下下个节点（second），交换原理如图1：

![5cefa93a03c8c52259.jpg][]

图1：交换节点示意图  
于是交换操作实现如下：

first->next = second->next;
    cur->next = second;
    cur->next->next = first;

**3.如何判断是否可以进行交换**  
链表的交换必须要保证  
当前节点的下一个节点以及下下个节点都必须存在，因此增加判断条件。

### 思路二：递归法 ###

很容易就能想到，对链表的每两个节点进行交换，实际上就是一种递归操作，如图3。

![5cefb26878b0c63365.jpg][]

图2：递归示意图

# C++ #

--------------------

*  思路一

/**
     * Definition for singly-linked list.
     * struct ListNode {
     * int val;
     * ListNode *next;
     * ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* swapPairs(ListNode* head) {
            
            if(head == nullptr || nullptr)
                return head;
            
            ListNode* result = new ListNode(0);
            result->next = head;
            ListNode* cur = result;
            while(cur->next != nullptr && cur->next->next != nullptr){
                
                ListNode* first = cur->next;
                ListNode* second = cur->next->next;
                
                //节点交换
                first->next = second->next;
                cur->next = second;
                cur->next->next = first;
                
                cur = cur->next->next;
            }
            
            return result->next;
            
        }
    };

*  思路二

# Python #

# 参考 #

转载于:https://www.cnblogs.com/Jessey-Ge/p/10993532.html

[5cefa93a03c8c52259.jpg]: https://i.loli.net/2019/05/30/5cefa93a03c8c52259.jpg
[5cefb26878b0c63365.jpg]: https://i.loli.net/2019/05/30/5cefb26878b0c63365.jpg