Description: 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.
Link: https://leetcode.com/problems/swap-nodes-in-pairs/
想法: 如果链表是空,或只有一个元素,直接返回head. 两个元素及以上时,相邻两个元素交换。以[1,2,3,4]为例,交换完[1,2] -> [2,1], 后面的[3,4]可以看做一个新的链表,进行同样的操作,所以可以用递归处理。这时候我们将问题简化,只考虑[1,2,3],那么我们会怎么做呢?
p = head.next #2 f = p.next #3 p.next = head head.next = f # f represents the elements followed p return p
我们把这段写进递归函数中,将f替换就可以了:
# 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): """ :type head: ListNode :rtype: ListNode """ def swap(l): if not l: return l if not l.next: return l p = l.next f = p.next p.next = l l.next = swap(f) return p return swap(head)
日期:2020-11-15 (It's a good start to be accepted by one submission, fighting! 冬天来了,居然还是很暖和)