构造一个递增有序的正整数链表,实现链表分解为一个奇数表和一个偶数表,之后再将两个链 表合并一个递减链表。
时间: 2024-10-23 10:04:59 浏览: 28
首先,我们需要构建一个递增有序的正整数链表,这个链表可以由一个节点类`ListNode`表示,包含一个整数值`val`和指向下一个节点的指针`next`。链表的构造通常是通过迭代或递归的方式添加节点。
接下来,我们创建两个辅助链表:`oddList`存储奇数节点,`evenList`存储偶数节点。遍历原始链表时,我们将每个节点值检查其奇偶性并相应地插入到对应的链表中。
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def split_list(head):
odd_head = ListNode(0)
even_head = ListNode(0)
current = head
odd = odd_head
even = even_head
while current:
if current.val % 2 == 0:
even.next = current
even = even.next
else:
odd.next = current
odd = odd.next
current = current.next
odd.next = None
even.next = None
return odd_head, even_head
```
最后,我们需要将这两个链表合并成一个递减链表。这可以通过先合并奇数链表和偶数链表,然后遍历整个链表生成新的节点,并更新它们的指针方向:
```python
def merge_sorted_lists(odd, even):
merged = ListNode(0)
tail = merged
while odd and even:
if odd.val > even.val:
tail.next = odd
odd = odd.next
else:
tail.next = even
even = even.next
tail = tail.next
if odd:
tail.next = odd
elif even:
tail.next = even
return merged.next
```
现在你可以通过调用`split_list`函数获取奇数表和偶数表,然后调用`merge_sorted_lists`合并它们得到递减链表。例如:
```python
# 创建原始链表示例
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
# 分解和合并操作
odd, even = split_list(head)
merged_decreased = merge_sorted_lists(odd, even)
```
阅读全文