网络异常,图片无法展示
|
题目地址(24. 两两交换链表中的节点)
题目描述
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例 1: 输入:head = [1,2,3,4] 输出:[2,1,4,3] 示例 2: 输入:head = [] 输出:[] 示例 3: 输入:head = [1] 输出:[1] 提示: 链表中节点的数目在范围 [0, 100] 内 0 <= Node.val <= 100 进阶:你能在不修改链表节点值的情况下解决这个问题吗?(也就是说,仅修改节点本身。)
思路
先获取一个Pre节点,然后再进行替换遍历
代码
- 语言支持:Python3
Python3 Code:
# Definition for singly-linked list. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def swapPairs(self, head: ListNode) -> ListNode: startHead = ListNode(-1) startHead.next = head tempHead = startHead while tempHead.next and tempHead.next.next: #先获得Node1、Node2 node1 = tempHead.next node2 = tempHead.next.next #进行替换 tempHead.next = node2 node1.next = node2.next node2.next = node1 #移动指针 tempHead = node1 return startHead.next
复杂度分析
令 n 为数组长度。
- 时间复杂度:O(n)O(n)
- 空间复杂度:O(1)O(1)