重新排列单链表L的节点顺序,改变为L=(a1,an,a2,an-1,...,an/2,a1)。例如,给定L为(1,2,3,4),重新排列后为(1,4,2,3)
时间: 2023-05-30 16:06:01 浏览: 83
思路:
1. 首先找到链表的中间节点(可以使用快慢指针法),将链表分为前半部分和后半部分。
2. 将后半部分链表翻转。
3. 依次将前半部分节点和翻转后的后半部分节点交替连接起来。
代码实现:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def reorderList(head):
"""
:type head: ListNode
:rtype: void Do not return anything, modify head in-place instead.
"""
if not head or not head.next:
return
# 找到链表的中间节点
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 将链表分为前半部分和后半部分
head1 = head
head2 = slow.next
slow.next = None
# 将后半部分链表翻转
prev = None
cur = head2
while cur:
next_node = cur.next
cur.next = prev
prev = cur
cur = next_node
head2 = prev
# 依次将前半部分节点和翻转后的后半部分节点交替连接起来
while head1 and head2:
next_node1 = head1.next
next_node2 = head2.next
head1.next = head2
head2.next = next_node1
head1 = next_node1
head2 = next_node2
```
时间复杂度:$O(n)$
空间复杂度:$O(1)$