signed

QiShunwang

“诚信为本、客户至上”

leetcode 24.两两交换链表中的节点 思路详解附代码

2021/5/15 0:33:14   来源:

### 解题思路

1.先将特殊情况,链表长度为0(直接返回NULL)或1(返回head)的情况处理。

2.定义指针p1指向第一个结点,定义指针p2指向第二个结点,然后定义lastNode结点指向上一次交换之后的第二个结点。

3.使用while循环,判断条件是p2指针是不是为NULL,如果是的话,不进入循环。不是NULL,进入之后先判断lastNode是不是空的,不是空的直接将其next指向上一次循环的p2结点。如果是空的,表示是第一次进入循环,不做处理。

4.p1和p2指针交换逻辑:先将p1的next指向p2的next,而后将p2的next指向p1。接着,将p1更新为其next结点,因为其next结点是下一对两个结点的第一个结点,然后将p2更新为p1的next结点即可。

5.判断更新完之后,p1和p2有一个为null就跳出循环(没有继续的必要了)。

 

### 代码

 

```cpp

/**

 * 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) {}

 * };

 */

 

class Solution {

public:

   //交换链表相连的两个结点

   ListNode* swapPairs(ListNode* head) {

    if(head == NULL || (head != NULL && head -> next == NULL)){ //表示空结点

        return head; 

    }

    

    //交换两个结点

    ListNode* p1 = head;

    ListNode* p2 = p1 -> next;

    

    ListNode* lastNode = NULL;

    

    ListNode* reNode = p1 -> next;

    

    //使用while循环实现交换结点

    while(p2 != NULL){  //表示p1的下一个结点不是null的就可以交换

        

        if(lastNode != NULL){  //表示有上一个结点,那么其next指针指向p1

             lastNode -> next = p2; 

        }

        

        //将p1结点的下一个设置为p2的下一个

        p1 -> next = p2 -> next;

        //将p2结点的下一个指向p1

        p2 -> next = p1;

        

        lastNode = p1;  //记录p1结点位置,为下一次循环做准备 

        

        //更新p1结点

        p1 = p1 -> next;

        if(p1 == NULL){//表示没有下一个了,直接跳出循环

            break;

        }

        

        //更新p2结点 

        p2 = p1 -> next;

        if(p2 == NULL){//如果p2等于null,表示链表是单数长度,直接跳出循环

            break; 

        } 

        

    } 

    

    return reNode;

}

};

```