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

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

思路

思路1：递归。

通过递归方式两两交换链表中的节点。如果链表为空，或者只有一个节点，则不做处理。

思路2：迭代法。构造一个dummy节点，每次交换两个节点：

假如交换之前的节点关系是temp -> node1 -> node2，交换之后的节点关系要变成temp -> node2 -> node1，因此需要进行如下操作:

temp.next = node2
node1.next = node2.next
node2.next = node1

Code

代码1：

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

	pre := head
	cur := head.Next
	next := head.Next.Next
	cur.Next = pre
	pre.Next = swapPairs(next)

	return cur
}

代码2：

func swapPairs(head *ListNode) *ListNode {
	dummyHead := &ListNode{Val: -1, Next: head}
	temp := dummyHead
	for temp.Next != nil && temp.Next.Next != nil {
		node1 := temp.Next
		node2 := temp.Next.Next
		temp.Next = node2
		node1.Next = node2.Next
		node2.Next = node1
		temp = node1
	}

	return dummyHead.Next
}