给定一个链表,对链表进行分隔,使得所有奇数都在单链表的左边,所有偶数都在单链表的右边。应当保留两个分区中每个结点的初始相对位置。示例:输入: head = 1->4->3->2->5->8。输出: 1->3->5->4->2->8。
时间: 2023-08-07 16:14:06 浏览: 131
好的,这是一道链表操作的题目。我可以给你一种解法,使用双指针来对链表进行分隔。具体步骤如下:
1. 定义两个指针 odd 和 even,分别指向奇数链表和偶数链表的头结点。
2. 遍历原链表,对于每个结点,如果它是奇数结点,就将它插入奇数链表的尾部;如果它是偶数结点,就将它插入偶数链表的尾部。
3. 遍历完成后,将偶数链表头结点连接到奇数链表尾结点。
具体实现可以参考下面的代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head: ListNode) -> ListNode:
if not head:
return head
odd = odd_head = ListNode(0)
even = even_head = ListNode(0)
is_odd = True
while head:
if is_odd:
odd.next = head
odd = odd.next
else:
even.next = head
even = even.next
head = head.next
is_odd = not is_odd
even.next = None
odd.next = even_head.next
return odd_head.next
```
注意,这里需要额外定义两个头结点 odd_head 和 even_head,这是为了方便连接两个链表。同时,在遍历原链表时,需要记录当前结点是奇数结点还是偶数结点,可以使用一个布尔变量 is_odd 来实现。
阅读全文