构造一个递增有序的正整数链表,实现链表分解为一个奇数表和一个偶数表,之后再将两个链 表合并一个递减链表。
时间: 2024-10-23 20:04:59 浏览: 41
C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
首先,我们需要构建一个递增有序的正整数链表,这个链表可以由一个节点类`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)
```
阅读全文