LeetCode题解-24. 两两交换链表中的节点

发表于 分类于

题目描述

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

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

示例:

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

思路

两两交换，然后相连，画一遍图熟悉一下交换过程就可以开始敲了，使用哑节点更方便。

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode swapPairs(ListNode head) {
       if (head == null || head.next == null) {
           return head;
       }
       ListNode dummy = new ListNode(-1);
       dummy.next = head;
       ListNode current = head;
       ListNode nHead = dummy;
       ListNode next;
       while (current != null && current.next != null) {
           next = current.next;
           current.next = next.next;
           next.next = current;
           dummy.next = next;
           dummy = current;
           current = current.next;
       }
       return nHead.next;
   }

解法2

递归解法，见LeetCode题解

1
2
3
4
5
6
7
8
9
public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }