题目地址(24. 两两交换链表中的节点)

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

题目描述

  1. 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
  3. 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
  7. 示例 1：
  9. 输入：head = [1,2,3,4]
  10. 输出：[2,1,4,3]
  13. 示例 2：
  15. 输入：head = []
  16. 输出：[]
  19. 示例 3：
  21. 输入：head = [1]
  22. 输出：[1]
  27. 提示：
  29. 链表中节点的数目在范围 [0, 100] 内
  30. 0 <= Node.val <= 100
  34. 进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）

前置知识


公司

  • 暂无

思路

  • 迭代

image.png

  • 递归

image.png

关键点

  • 迭代法

将3号元素用临时节点存储起来
head的位置在经过换位置以后位置就移到了后面一位 所以说只需要移动一位 所以说在最后交换位置的时候只需要往后移动一位 这里困扰了半天😑

  • 递归法

设置中止条件 终止条件的next==null要在next.next ==null之前
递归调用方法 使每两个数字交换 交换完 原head成为next 原next 成为head 原head指向递归调用得到的新的newhead也就是上图中的 2->1->4 4->3->null

代码

  • 语言支持：Java

Java Code:

  • 迭代法 ```java

/**

  • Definition for singly-linked list.
  • public class ListNode {
  • int val;
  • ListNode next;
  • ListNode() {}
  • ListNode(int val) { this.val = val; }
  • ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  • } */ class Solution {
    1.  public ListNode swapPairs(ListNode head) {
    2.      //定义一个头结点 初始化 指向head
    3.      ListNode touNode = new ListNode(0,head);
    4.      //定义一个前置节点 指向头结点
    5.      ListNode pre = touNode;
    6.      //如果pre的下个元素及下下个都不是空的 则继续循环
    7.      while (pre.next != null && pre.next.next != null) {
    8.          //定义一个临时节点存储向上图中的3号元素
    9.          ListNode temp = head.next.next;
    10.          //步骤1
    11.          pre.next = head.next;
    12.          //步骤2
    13.          head.next.next = head;
    14.          //步骤3
    15.          head.next = temp;
    16.          //使pre = head 也就是往后移两位 为什么是两位呢 上面有解答
    17.          pre = head;
    18.          head = head.next;
    19.      }
    20.      return touNode.next;
    21.  }
    } ```
  • 递归法
    1. class Solution {
    2.       public ListNode swapPairs(ListNode head) {
    3.           //递归中止条件
    4.           if (head==null ||head.next == null){
    5.               return head;
    6.           }
    7.           //定义next节点在head后面
    8.           ListNode next = head.next;
    9.           //递归调用next.next 也就是head的下两个节点位置 返回的是下一个交换完位置的头结点
    10.           ListNode newNode = swapPairs(next.next);
    11.           //调转head和next的位置
    12.           next.next = head;
    13.           //让调转后的head指向递归调用的结果 也就是家换完位置的头结点 完成链表的连接
    14.           head.next = newNode;
    15.           return next;
    16.       }
    17.   }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：24. 两两交换链表中的节点 - 图3#card=math&code=O%28n%29&id=Cu9CH)
  • 空间复杂度：24. 两两交换链表中的节点 - 图4