7

LeetCode: 24. Swap Nodes in Pairs

 3 years ago
source link: https://mozillazg.com/2020/10/leetcode-24-swap-nodes-in-pairs.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

题目

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

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK