leetcode-024-Swap-Nodes-in-Pairs

发表于 | 更新于: | 分类于 |

leetcode-024-Swap-Nodes-in-Pairs 两两交换链表中的节点

1. 题目

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

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

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

2.解

四个需要注意的点吧：

  1. 给三个指针，分别指向两个待交换结点和他们的前驱结点
  2. 链表的两个特殊情况：[] and [1]
  3. 链表的两两交换结点操作
  4. 重置三个指针的位置
    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
    30
    31
    32
    33
    34
    35
    36
    37
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    class Solution:
        def swapPairs(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
    		
    		# 开一个常数空间的头结点
            new_head = ListNode(-1)
    		# pre始终指向待交换结点的前驱结点
            pre = new_head
            first = head
            
    		# 两种特殊情况：[] and [1]
            if head == None or head.next == None:
                return head
            else:   
                second = head.next

            while second:
    		
                # 两两交换结点的经典操作
                pre.next = second
                first.next = second.next
                second.next = first
                
    			# 重置三个结点
                pre = first
                first = pre.next
                second = pre.next.next if first else None
            return new_head.next