AcWing
  • 首页
  • 题库
  • 题解
    • LeetCode
    • AcWing
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

LeetCode 24. Swap Nodes in Pairs    原题链接    中等

作者: 作者的头像   wzc1995 ,  2018-03-28 22:54:14 ,  阅读 1041


4


3

题目描述

给定一个单向链表,依次交换每一对相邻的两个结点,返回修好后的链表头结点。

链表结点的数据结构:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

样例

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

额外要求

  • 不得修改链表中结点的 val 值,仅可以使用常数的空间。

算法

(模拟) $O(L)$
  1. 添加虚拟头结点 dummy。
  2. 定义 cur 指针初始指向 dummy。
  3. 定义 first 为 cur->next,second 为 first->next;若 first 或 second 为空,则终止循环。
  4. 按照一定的次序,修改 cur、first 和 second结点的 next 指针,具体参见代码。
  5. 将 cur 指向修改后的 first,接着从第3步循环。

时间复杂度

  • 仅遍历一遍所有结点,所以是 $O(L)$。

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(0);
        dummy -> next = head;
        ListNode* cur = dummy;

        while (cur != NULL) {
            ListNode* first = cur -> next;
            if (first == NULL)
                break;

            ListNode* second = first -> next;
            if (second == NULL)
                break;

            // 按照一定的次序,交换相邻的两个结点。
            cur -> next = second;
            first -> next = second -> next;
            second -> next = first;

            cur = first;
        }
        return dummy -> next;
    }
};

评论列表:

你确定删除吗?

© 2018-2019 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息