上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
}
};
python3 解法, 执行用时: 64 ms, 内存消耗: 23.1 MB, 提交时间: 2022-08-10 16:06:56
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
# 寻找链表中点 + 链表逆序 + 合并链表
if not head:
return
mid = self.middleNode(head)
l1 = head
l2 = mid.next
mid.next = None
l2 = self.reverseList(l2)
self.mergeList(l1, l2)
def middleNode(self, head: ListNode) -> ListNode:
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseList(self, head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
nextTemp = curr.next
curr.next = prev
prev = curr
curr = nextTemp
return prev
def mergeList(self, l1: ListNode, l2: ListNode):
while l1 and l2:
l1_tmp = l1.next
l2_tmp = l2.next
l1.next = l2
l1 = l1_tmp
l2.next = l1
l2 = l2_tmp
python3 解法, 执行用时: 84 ms, 内存消耗: 23.2 MB, 提交时间: 2022-08-10 16:06:11
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
# 利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。
if not head:
return
vec = list()
node = head
while node:
vec.append(node)
node = node.next
i, j = 0, len(vec) - 1
while i < j:
vec[i].next = vec[j]
i += 1
if i == j:
break
vec[j].next = vec[i]
j -= 1
vec[i].next = None
