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

题目地址 #

解题思路 #

参考 https://leetcode.cn/problems/swap-nodes-in-pairs/solutions/444474/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91/

递归法 #

可以通过递归的方式实现两两交换链表中的节点。递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

用head表示原始链表的头节点，新的链表的第二个节点，用newHead表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是newHead.next。令head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为head的下一个节点。然后令newHead.next = head，即完成了所有节点的交换。最后返回新的链表的头节点newHead。

⚠️好吧，再理解一下，关于递归，我只关注我这一层要干什么，返回什么，至于我的下一层（规模减 1），我不管，我就是一个甩手掌柜🙈。

我其实只需要关心第一层，也就是节点1和节点2的交换，把节点2的next指向节点1，节点2的next给下一层也就是递归函数。而我最后返回的应该是头结点，其实也就是原始节点的节点2。

迭代法 #

TODO

具体实现 #

Go迭代

package main

import (
	"fmt"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
	if head == nil {
		return head
	}

	dummy := &ListNode{
		Val:  0,
		Next: head,
	}

	curr := dummy
	// 如果是链表长度是奇数那就没有必要交换，只有偶数才需要交换，所以这里的判断条件是 &&
	// 这里不能用一个临时参数，因为链表指针后的值会变化
	for curr.Next != nil && curr.Next.Next != nil {
		tmp := curr.Next
		tmp1 := curr.Next.Next.Next

		curr.Next = curr.Next.Next
		curr.Next.Next = tmp
		curr.Next.Next.Next = tmp1

		// 这里也可以直接写成 curr = tmp
		curr = curr.Next.Next
	}

	return dummy.Next
}

func main() {
	x := swapPairs(&ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val:  4,
					Next: nil,
				},
			},
		},
	})
	fmt.Println(x)
}

Go递归

package main

import (
	"fmt"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	newHead := head.Next
	head.Next = swapPairs(head.Next.Next)
	newHead.Next = head
	return newHead
}

func main() {
	x := swapPairs(&ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val:  4,
					Next: nil,
				},
			},
		},
	})
	fmt.Println(x)
}