24. 两两交换链表中的节点_链队列交换节点

题目描述

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

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

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：
输入：head = []
输出：[]

示例 3：
输入：head = [1]
输出：[1]

题目解析

1、递归解法

我的理解就是将递归作为一个结果单独看待，图解：

“其余”代表递归结果，表明已经是做完调整顺序的结果，只需要调整当前的head、next即可。

代码实现：

public ListNode swapPairs(ListNode head) {

          if(head == null || head.next == null){
              return head;
          }
          ListNode p = head.next;
          head.next = swapPairs(p.next);
          p.next = head;
          return p;

      }
1
2
3
4
5
6
7
8
9
10
11

2、迭代算法

迭代的思路比较简单，就是将每两个数为一组，进行两两交换，例如1->2->3->4,(1,2)为一组交换，(3,4)为一组交换，但是有一个细节需要注意：1、2交换完2指向1，1指向3；3、4交换，但是这时需要将1指向4，所以需要记录一个前序节点。

private ListNode swapPairs(ListNode head){

          if (head == null) {
              return null;
          }
          ListNode p = head;
          ListNode res = head.next;
          ListNode t = null;//保存节点的前一个节点
          while (p != null && p.next != null) {

              ListNode q = p.next;
              p.next = q.next;
              q.next = p;
              //如果t为null，说明是第一个节点
              if (t != null) {
                  t.next = q;
              }
              t = p;
              p = p.next;
          }
          //防止结果是基数是最后一个节点漏掉
          if (p == head) {
              return head;
          }else {
              return 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

3、利用队列或者栈

思路就是每两个数为一组放进队列里，但是顺序要相反。然后将队列的数一一取出重新组合。注意点，最后一个对象的next一定要置为null，不然它指向了另外的对象，会造成死循环。

private ListNode swapPairs(ListNode head){



          ListNode p = new ListNode();
          ListNode res = p;
          Queue<ListNode> queue = new ArrayDeque<>();
          while (head != null && head.next != null) {
              queue.add(head.next);
              queue.add(head);
              head = head.next.next;
          }
          if (head != null) {
              queue.add(head);
          }
          while (!queue.isEmpty()) {
              p.next = queue.poll();
              p = p.next;
          }
          p.next = null;
          return res.next;
      }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

性能分析

三种算法的时间复杂度都是O(n)，前两种算法的空间复杂度是O(1)，第三种需要一个队列辅助，所以空间复杂度是O(n)。

有不足之处多多指教
公众号：“计算机基础爱好者”
关注公众号回复“leetcode”，有leet-java.pdf书籍