星尘

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

发表于 更新于 分类于

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

题目

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

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

示例 1:

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

示例 2:

1
2
输入：head = []
输出：[]

示例 3:

1
2
输入：head = [1]
输出：[1]

题解

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
29
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(next=head)
        cur = dummy
        # https://raw.githubusercontent.com/rexyan/warehouse/master/20210902135729.png
        while cur.next and cur.next.next:
            tmp1 = cur.next
            tmp2 = cur.next.next.next

            # 步骤1
            cur.next = cur.next.next
            # 步骤2
            cur.next.next = tmp1
            # 步骤3
            cur.next.next.next = tmp2

            cur = cur.next.next

        return dummy.next
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
type ListNode struct {
	Val int
	Next *ListNode
}


func swapPairs(head *ListNode) *ListNode {
	dummy := ListNode{
		Next: head,
	}
	cur := &dummy

	for cur.Next!=nil && cur.Next.Next!=nil {
		tmp1 := cur.Next
		tmp2 := cur.Next.Next.Next

		// 步骤1
		cur.Next = cur.Next.Next
		// 步骤2
		cur.Next.Next = tmp1
		// 步骤3
		cur.Next.Next.Next = tmp2

		cur = cur.Next.Next
	}
	return dummy.Next
}

变体

总结

参考