【LeetCode每日一题】24. Swap Nodes in Pairs

公众号-不为谁写的歌

发布于 2020-07-28 15:36:19

3030

发布于 2020-07-28 15:36:19

文章被收录于专栏：桃花源记桃花源记

问题描述

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.

给定一个链表，依次交换其邻接的两个节点，返回最终结果。

不能通过修改节点的值来实现交换。

题解

一般情况下，链表的题可以通过转化成数组进行求解。假如这里没有条件限制，我们可以：

遍历链表，将链表中节点的值保存在数组中；
对数组进行两两交换；
将数组交换后的结果，重新变成链表存储。

但是这里规定不能通过修改链表节点的值，所以这里主要考察的就是对指针的操作。

实际的解法是：

设立一个头结点，方便后续操作；
首先考虑Corner case，如果链表为空，或者只有一个节点的情况下，直接返回原链表；
一般情况，因为涉及到链表节点的交换，交换的对象是相邻的两个节点，所以要保证两个节点不为空：
1. 循环条件 while (node->next && node->next->next) ;node 初始化为新声明的头结点；
2. 相邻两个节点的交换，要保证链表的完整性，比如1->2->3->4:声明头结点后，链表为-1->1->2->3->4,node初始化指向-1；
3. 首先，将声明一个指针temp指向2（node->next->next）
4. 断链，让node->next的next指向temp的next，变成-1->1->3->4,同时2也指向3；
5. 让2指向1：temp->next = node->next，
6. 最后，将node->next指向2，完成单次相邻节点的交换；
7. 更新node指针，指向下一轮要交换节点的前向节点。

/**
 * 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 || !head->next) return head;
        
        ListNode *first = new ListNode(-1), *node = first;
        first->next = head;
        
        while (node->next && node->next->next){
            ListNode *temp = node->next->next;
            node->next->next = temp->next;
            temp->next = node->next;
            node->next = temp;
            
            node = node->next->next;

        }
        
        return first->next;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/07/24 ，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js