[0024] 两两交换链表中的节点

title: “[0024] 两两交换链表中的节点”
tags:

leetcode
题解
链表
categories:
leetcode
题解
author:
黄宁
comments: true
updated: true
permalink:
mathjax: true
top: false
description: …
date: 2020-04-17 11:09:24

[0024] 两两交换链表中的节点

题目描述

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

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

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

Related Topics

链表

题目解析

[请一句话描述题目…]

不确定性

方法一：三指针迭代法

分析

设定一个指针指向奇数节点，另一个指针指向偶数节点，对两个节点进行交换

思路

建立一个前驱节点，并使用pre指针指向它
建立指针start指向奇数节点和指针end指向偶数节点
令pre的后继节点为end，令start为end的后继节点
调整3个指针的位置，顺序迭代，指导前驱节点pre的后继不存在（偶数个节点），或pre的后继的后继不存在（奇数个节点）

注意

链表中节点个数可能是奇数个或偶数个

知识点

链表中节点的插入

复杂度

时间复杂度 O(n)
空间复杂度 O(1)

代码

ListNode* swapPairs(ListNode* head) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* pre = dummy;
    while (pre->next && pre->next->next){
        ListNode* start = pre->next;
        ListNode* end = start->next;
        pre->next = end;
        start->next = end->next;
        end->next = start;
        pre = start;
    }
    return dummy->next;
}

方法二：递归法

分析

交换的每一步都是类似的，将前一个节点的next指针指向后一个节点的后继节点，让后一个节点的next指针指向前一个节点

思路

定义指针start作为前一个节点，end作为后一个节点
start的后继是“已经交换好的链表的头节点”，这是就要再次进入递归体
end的后继是start
递归的出口是当前节点或当前节点的后继节点为空

注意

在交换完成后，后一个节点成为了前一个节点，因此需要返回的是后一个指针

知识点

递归
链表中节点的插入

复杂度

时间复杂度 O(N)
空间复杂度 O(N)

代码

 ListNode* swapPairs(ListNode* head) {
     //递归的出口
     if (!head || !head->next){
         return head;
     }
     ListNode* start = head;
     ListNode* end = head->next;
     //主体部分，和插入类似，先连后边节点，再连前边节点
     //可以看作第一个节点的后一个节点是，后面已经交换好的链表的头节点
     start->next = swapPairs(end->next);
     end->next = start;
     //因为后一个节点被换到前一个位置，所以返回后一个节点
     return end;
 }