首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode题目24:两两交换链表中的节点

LeetCode题目24:两两交换链表中的节点

作者头像
二环宇少
发布2020-08-13 15:38:31
3560
发布2020-08-13 15:38:31
举报

原题描述

+

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

注意:你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例

输入:1->2->3->4
输出:2->1->4->3

原题链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs

思路解析

+

这道题用到的指针数量比较多,很一不小心容易乱。关键点在于两个节点交换之后,一定要能够和后面未操作的部分再度连起来,这就需要记住四个位置。

  1. 第一个要交换的节点位置(靠前),用first指针指代;
  2. 第二个要交换的节点位置(靠后),用second指针指代;
  3. 处于second后部,未被操作的子链表头位置,用head指代;
  4. 处于first前部子链表尾部位置,用prev指代。

然后,你才可以操作指针,形成prev->second->first->head的结构,如下图所示。

为了便于操作,代码中还是要加一个哑结点。

复杂度分析

+

  • 时间复杂度:
  • 空间复杂度:

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) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *p = dummy, *first, *second;
        while (head && head->next) {
            first = head;
            second = head->next;
            head = second->next;

            p->next = second;
            second->next = first;
            first->next = head;

            p = p->next->next;
        }

        return dummy->next;
    }
};
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-06-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 互联网西门二少 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档