将链表的前半部分和后半部分交换
时间: 2024-03-30 18:10:20 浏览: 6
这道题可以分为以下几个步骤:
1. 找到链表的中间节点,可以使用快慢指针的方法。
2. 将链表的后半部分进行反转,可以使用迭代或递归的方法。
3. 将链表的前半部分和反转后的后半部分进行交换。
下面是Python的代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reorderList(head: ListNode) -> None:
if not head or not head.next:
return head
# 找到链表的中间节点
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 反转链表的后半部分
prev, cur = None, slow
while cur:
temp = cur.next
cur.next = prev
prev = cur
cur = temp
head2 = prev
# 将链表的前半部分和反转后的后半部分进行交换
p1, p2 = head, head2
while p2.next:
temp1, temp2 = p1.next, p2.next
p1.next = p2
p2.next = temp1
p1, p2 = temp1, temp2
p1.next = p2
```
时间复杂度为O(n),空间复杂度为O(1)。