题目¶
原题地址：https://leetcode.com/problems/swap-nodes-in-pairs/
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
解法¶
遍历链表，通过修改节点的 next 属性交互节点位置¶
遍历然后交换节点位置的方法有几个场景需要处理：
节点个数为偶数，此时两两交换即可（当前节点指向上一个节点，上一个节点指向下下个节点）:
1->2->3->4->5->6 2->1->4->3->6->5
节点个数为奇数，此时前面的偶数个节点按上面的方法进行交换，但是最后三个节点需要特殊处理，上个节点指向下个节点即可不需要指向下下个节点（因为不存在下下个节点）:
1->2->3->4->5 2->1->4->3->5
节点个数 < 2，此时无法做交换，直接返回原始链表即可:
1 1
这个方法的 Python 代码类似下面这样:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def swapPairs(self, head):
# 节点个数 < 2
if head is None or head.next is None:
return head
new_head = head.next
current = head.next
pre = head
_next = current.next
while True:
if current is None:
break
# 将当前节点指向上个节点
current.next = pre
# 当前节点是偶数节点的最后一个节点或者是奇数节点的倒数第二个节点
if _next is None or _next.next is None:
pre.next = _next
break
else:
pre.next = _next.next
pre = _next
current = _next.next
_next = current.next
return new_head
递归方法¶
递归的方法就是从头到尾两两节点进行交换，每次交换后返回的新 head 节点用来跟上个交换结果进行连接。
这个方法的 Python 代码类似下面这样:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def swapPairs(self, head):
# 节点个数 < 2
if head is None or head.next is None:
return head
# 第二个节点移到了第一位作为新的 head 节点
new_head = head.next
# 第三个节点
_next = head.next.next
# 第二个节点指向第一个节点
head.next.next = head
# 第一个节点指向第三第四节点交换后的 head 节点
head.next = self.swapPairs(_next)
return new_head
Comments