【Leetcode】【Medium】Swap Nodes in Pairs

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

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

解题思路：

传统的链表操作题，需要注意如果结点不是偶数，最后一个结点不需要交换，放在队尾。

先条件：head不为空；head至少包含两个结点；

后条件：返回指向新链表第一个结点的指针；原链表结点全部加入新链表中，并且偶数对结点两两互换；新旧链表的结点数一致。

不变式：1、新建一个newhead指针，newhead->next永远指向新链表的头部；

　　　　2、新建一个newlist指针，newlist永远指向新链表的最后一个结点；

　　　　3、newlist->next始终为NULL；

　　　　4、head指针永远指向还未被操作的旧链表第一个结点；

　　　　5、新链表上的结点数加上旧链表剩余的结点数之和，应该和原链表结点数一致；

当head为空时，循环结束，每次循环：

　　　　1、将head中的结点按对取出~交换~插入newlist末端

　　　　2、若head只剩一个结点不够一对，则直接插入newlist末端；

解题步骤：

1、新建preHead结点，新建newlist指针；

2、按照不定式分析，开始循环，循环结束标志为head为空：

　　（1）如果当前head只剩一个结点，则将其插入newlist后，并结束循环；

　　（2）取出待操作的两个结点，head后移两位；

　　（3）将这两个结点反转插入newlist中

3、释放preHead，返回newlist；

代码1：

 /**

  * 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 == NULL || head->next == NULL)

             return head;

         */

         ListNode* newhead = new ListNode();

         ListNode* newlist = newhead;

         ListNode* preNode = NULL;

         while (head != NULL) {

             if (head->next == NULL) {

                 newlist->next = head;

                 break;

             }

             preNode = head;

             head = head->next->next;

             preNode->next->next = preNode;

             newlist->next = preNode->next;

             newlist = preNode;

             newlist->next = NULL;

         }

         head = newhead->next;

         delete newhead;

         return head;

     }

 };

代码2，使用二维指针：

基本逻辑实现：

 ListNode **p = &head;

 while (*p && (*p)->next) {

     // n表示待交换的两个结点中，后一个结点

     ListNode* n = (*p)->next;

     (*p)->next = n->next;

     n->next = *p;

     p = &(*p)->next;

 }

由于二维指针p一直在操作当前需要交换的结点，不断向后迭代，而head指针此时指向的是链表中第二个结点（前两个交换）；

因此上述代码唯一的问题是，没有指针指向头结点，无法返回...

所以我们希望在第一轮交换时，将head结点重新指向交换后的第一个结点。观察到第一轮交换时，*p其实就代表head，操作*p的指向，就是操作head的指向。

所以，最终代码为：

 /**

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

         ListNode **p = &head;

         while (*p && (*p)->next) {

             ListNode* n = (*p)->next;

             (*p)->next = n->next;

             n->next = *p;

             *p = n;

             p = &(*p)->next->next;

         }

         return head;

     }

 };

巴特西

【Leetcode】【Medium】Swap Nodes in Pairs

最新文章

热门文章