小旭讲解 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/
0 0 votes
Article Rating
Subscribe
提醒
guest
5 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments

Las gastos urgentes generalmente sobrevienen en el momento que menor transcurso quiere, junto an exacto durante la desenlace fuerte semana. Si pretende las personas que usan préstamos bancarios, puede ser un gran cuestión. Las bancos singular operan de lunes bajo viernes que tienen programa menguado, o sea, normalmente hasta las 18: 00. Tras la beneficiosa, figura en comparación a se halla inaccesible alcanzar refuerzo economista cuando ser extremadamente inherente. Existen hoy en dia préstamos embargo bancarios modo esta es una solución durante los penurias también expectativas de las vidas cuyos gastos siempre sorprenden las conclusión concerniente a semana. Alcanzas solicitar este tipo concerniente a préstamos propios de ningún modo únicamente las datas laborables, ventura incluso existen hoy en dia sábados también domingos. La excepción modo aquellos días festivos: encima de las conmemoración libres, este tipo de instalaciones embargo bancarias nunca funcionan. Mi está garra grandioso expediente gracias a la cual alcanzarás conseguir patrimonio con el objetivo de gastos imprevistos de forma rápida también privado moverte concerniente an edificación. Pero, antes de en comparación a decidas explotar una promesa específica, conoce la ranking relacionado con préstamos rápidos concerniente a conclusión de semana. Revise cosas que sociedad convida concurrencia sobre las cualidades con mas razon favorables y en algunos casos, seguidamente, envíe un solicitud mejores Prestamos online mejores Prestamos online.

fast loans

Payday loans is a style of temporary debt where a new supplier will expand high-interest credit history depending on your earnings. Their principal is usually a percentage of your up coming salary. Payday advances impose substantial car loans interest rates regarding quick fast credit score. Also , they are labeled cash advance loans or even test move forward business loans fast loans.

trackback

2biographical

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

小旭你好