将链表的前半部分和后半部分交换
时间: 2024-03-30 12:10:20 浏览: 19
这个问题需要先确定链表的长度,然后再将链表的前半部分和后半部分交换。
具体的做法可以分为以下几步:
1. 遍历链表,确定链表的长度;
2. 将链表分成两部分,前半部分和后半部分;
3. 将前半部分的尾节点指向后半部分的头节点,后半部分的尾节点指向前半部分的头节点;
4. 返回交换后的链表。
代码示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def swapList(head):
# 遍历链表,确定链表的长度
length = 0
node = head
while node:
length += 1
node = node.next
if length < 2:
return head
# 将链表分成两部分,前半部分和后半部分
mid = length // 2
pre = None
cur = head
for i in range(mid):
pre = cur
cur = cur.next
pre.next = None
left = head
right = cur
# 将前半部分的尾节点指向后半部分的头节点,后半部分的尾节点指向前半部分的头节点
node = right
while node.next:
node = node.next
node.next = left
head = right
# 返回交换后的链表
return head
```
时间复杂度为 $O(n)$,空间复杂度为 $O(1)$。