LeetCode: 24. Swap Nodes in Pairs

题目

原题地址: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.

解法

递归方法

递归的方法就是从头到尾两两节点进行交换,每次交换后返回的新 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

comments powered by Disqus