24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

链表天然具有递归属性，可以把后面的数字当做整体来看，有点类似高中的整体受力法。

其中我们应该关心的主要有三点：

  1. 返回值
  2. 调用单元做了什么
  3. 终止条件

在本题中：

  1. 返回值：交换完成的子链表
  2. 调用单元：设需要交换的两个点为 head 和 next，head 连接后面交换完成的子链表(递归核心)，next 连接 head（翻转核心），完成交换

  3. 终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换 ```go //递归法，通法，经典递归思路，时间复杂度On,空间复杂度On func swapPairs(head ListNode) ListNode { if head == nil || head.Next == nil {

    1.  return head  //当后面的数字为空，或者为一个时，直接返回当前指针数
    2.  //终止条件：链表只剩一个节点或者没节点了，没得交换了。返回的是已经处理好的链表

    }

    //一共三个节点:head, temp, swapPairs(temp.next) //下面的任务便是交换这3个节点中的前两个节点 temp := head.Next //head表示头节点，temp表示第二个节点，暂存数字，链表都有:= head.Next = swapPairs(temp.Next) //递归核心，去掉swap函数，就不走了，只交换了前两个数 //head.Next = temp.Next // 交换后的新节点为head节点的下一跳，其实就是temp前，head后 temp.Next = head //翻转核心，temp下一跳指向本次前数 //根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分

    return temp //返回新头结点，后节点 }

```go
//简化代码：递归法，时间复杂度On,空间复杂度On
func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head  
    }

    cur := head
    temp := cur.Next

    cur.Next = swapPairs(temp.Next)     //新的脚步cur.Next
    temp.Next = cur                     //两两前进，记录原脚步

    return temp                         //这样就可以理解返回temp，因为temp是前脚
}

思路

  • 设置虚拟头结点 fack，因为真实头结点要换人，设置了 fack 后，fack.next 就能找到头结点。
  • 开启 while 循环，一对结点的交换有三个指针要改变，见下图。
  • 指针推进，准备交换下一对结点。
  • 最后返回 fack.next 。

  • image.png ```go //简化代码，迭代法，时间复杂度On,空间复杂度O1,就是头插法 func swapPairs(head ListNode) ListNode { dummy := &ListNode{Next: head} prev := dummy

    cur := head for cur != nil && cur.Next != nil {

      temp := cur.Next
  cur.Next = temp.Next
  temp.Next = prev.Next
  prev.Next = temp

  prev = cur                        //cur是两个一动，手动赋值前进；            
  cur = cur.Next                    //注意原来是cur->temp; 现在是temp->cur->新的

    } return dummy.Next }

```