Halo

A magic place for coding

0%

LeetCode解题报告（31）-- 24. Swap Nodes in Pairs

Posted on Edited on Valine:

Problem

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

Example:

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

Note:

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

Analysis

2018.01.12

  这道题考察的是关于链表的操作，难点在于它要求交换相邻的两个节点。同时题目要求不能更改节点的值，我们只能通过更改节点之间的指针来实现。
  因为是交换相邻的两个节点，因此我们需要使用两个指针分别指向先后两个节点。如果链表的节点数是偶数，那么每两个交换；如果链表的节点数是奇数，那么最后一个节点则不需要操作。如果给出两个节点，要求交换，这个操作并不难，first->next = second->next; second->next = first即可实现。难度在于如果切换至下一对节点。首先我们需要判断后面是否有节点，这里对first判断是否为null即可。循环的退出条件是只剩最后一个节点或后面没有节点。
  运行后发现仍然报错了，出错的原因是，上一对的first应该指向的是当前对的second。如果需要在上一对处理的时候判断，那么将会增加大量的代码。这里我将判断放到了当前对中，因此只需要额外增加一个变量last来表示上一对的first。在当前对中，直接将last->next = second来完成两对之间的连接。这个办法显然快很多。
  至此，整个算法思路就很明确了。同时要注意两个问题：

  1. 当链表长度小于等于2的时候，直接返回。
  2. 我们需要用一个变量result来返回交换后的表头，因为交换后的表头一定是第一对中的second，所以可以直接赋值result = second。

更新于2021.03.21

  一年多之后又碰到了这道题目，解决这道题目的思路还是一样的，但是在代码层面上比之前更加统一以及易懂。交换两个元素，假设结构是a->b->c->d。这里假设我们要交换b和c，我们的做法分解为三步：

  1. 先使用一个变量存储c，因为在交换完这一对之后，b要指向c后面的元素d，所以要先记下来，用于访问d；
  2. 然后改变b的指向，b指向d；
  3. 然后c指向b；
  4. 最后是a指向c。

  通过上面四个步骤就可以完成，因为我们每次都是从a开始的，所以要保证a->next和a->next->next 都不为空。

  同时，还有一个技巧可以使用，当处理第一对的时候，我们会发现没有a，这种情况下直接新增一个dummy节点即可。这样处理后所有的情况都可以统一处理了。

Code

2018.01.12

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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 *first;
        ListNode *second;
        if (head == NULL || head->next == NULL) {
            return head;
        }

        first = head;
        second = head->next;
        ListNode* result = second;
        ListNode *last = first;

        while (second != NULL) {
            last->next = second;
            first->next = second->next;
            second->next = first;
            last = first;
            first = first->next;
            if (first == NULL) {
                break;
            }
            second = first->next;
        }

        return result;
    }
};

运行时间：约0ms，超过100%的CPP代码。

2021.03.21

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 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) {
        ListNode *dummy = new ListNode(-1);
        ListNode *pre = dummy;
        
        dummy->next = head;
        
        while (pre->next && pre->next->next) {
            ListNode* t = pre->next->next;
            pre->next->next = t->next;
            t->next = pre->next;
            pre->next = t;
            pre = t->next;
        }
        return dummy->next;
    }
};

Summary

  这道题目考点还是链表的操作，相比起以前的插入删除，这道题的难度有所提高，做起来还是花了点时间。我的建议是关于链表的题目多在纸上画，模拟一下算法的过程，然后可以在程序中打印一下相关的值，同时牵涉到指针问题需要特别注意指针为空的情况。本题的分析就到这里，感谢您的支持！

Welcome to my other publishing channels