小旭讲解 LeetCode 24. Swap Nodes in Pairs
小旭讲解 LeetCode 24. Swap Nodes in Pairs

Problem

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.

题目

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

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

Video Explaination

B站视频源

YouTube视频源

Explaination

  • 分别利用递归与迭代的方式解决
  • 通过虚拟元素(Dummy Variable)避免边界情况的处理

Code

Iteration

/**
 * 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 = head, *pre = dummy;
        while (cur != nullptr && cur->next != nullptr) {
            // pre cur cur->next cnext->next
            ListNode* cnext = cur->next;
            cur->next = cnext->next;
            cnext->next = cur;
            pre->next = cnext;
            // pre cur->next cur cnext->next
            
            pre = cur;
            cur = cur->next;
        }
        return dummy->next;
    }
};

Complexity Analysis

Time Complexity: O(n)
Space Complexity:O(1)

Recursive

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void helper(ListNode* cur, ListNode* pre) {
        if (cur == nullptr || cur->next == nullptr) return;
        ListNode* cnext = cur->next;
        cur->next = cnext->next;
        cnext->next = cur;
        pre->next = cnext;
        pre = cur;
        cur = cur->next;
        helper(cur, pre);
    }
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        helper(head, dummy);
        return dummy->next;
    }
};

Complexity Analysis

Time Complexity: O(n)
Space COmplexity:O(n)


题目:https://leetcode.com/problems/swap-nodes-in-pairs/

欢迎分享,引用。若转载,请联系我,谢谢配合。
本文地址:https://qoogle.top/xiaoxu-explaination-leetcode-24-swap-nodes-in-pairs/
最后修改日期:2020年6月18日

作者

留言

d=====( ̄▽ ̄*)b 

小旭你好

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。