两两交换链表中的节点

发表于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

LeetCode每日一题，24. Swap Nodes in Pairs

先看题目描述

大意就是给定一个链表，两两交换其中相邻的节点，然后返回交换后的链表

算法和思路

算法流程

  • 先判断链表是否为空，或者只有一个节点，则不需要操作，直接返回 head
  • 初始化 pre = null，node = head，res = head.next
  • 然后开始移动 node 遍历链表，并在途中交换相邻节点 node 与 node.next
    • 交换相邻节点需要三个参数：要交换的 first 节点和 last 节点，还有 first 的前置节点 pre，交换操作如下：
      • 若 last 为空，则无需交换，直接返回
      • 令 temp = last.next
      • last.next = first
      • first.next = temp
      • 若 pre 不为空，则 pre.next = last
    • 交换 node 与 node.next 后，node 变为较后节点，令 pre = node，node = node.next
  • 持续上述操作直至 node 为空，交换后的链表的头节点为 res，即一开始的 head.next，返回 res即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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 {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = null;
        ListNode node = head;
        ListNode res = head.next;
        while (node != null) {
            swao(node, node.next, pre);
            pre = node;
            node = node.next;
        }
        return res;
    }

    private void swao(ListNode first, ListNode last, ListNode pre) {
        if (last == null) return;
        ListNode temp = last.next;
        last.next = first;
        first.next = temp;
        if (pre != null) pre.next = last;
    }
}