构造一个递增有序的正整数链表,实现链表分解为一个奇数链表和一个偶数链 表,之后再将两个链表合并一个递减链表代码
时间: 2024-10-24 20:12:48 浏览: 36
创建一个递增有序的正整数链表,并将其拆分为奇数链表和偶数链表,然后将这两个链表合并成一个递减链表,这个过程可以分为以下几个步骤:
1. **创建链表**:
首先,你需要定义一个Node结构体,包含一个值`value`和指向下一个节点的指针`next`。
```python
class ListNode:
def __init__(self, value=0):
self.value = value
self.next = None
```
2. **构造递增有序链表**:
遍历输入的数字序列,创建一个新的链表节点并连接它们。
```python
def build_sorted_list(numbers):
head = ListNode()
current = head
for num in sorted(numbers):
current.next = ListNode(num)
current = current.next
return head.next
```
3. **拆分链表**:
创建两个新的头节点,`odd_list`和`even_list`,分别用于存储奇数和偶数链表。然后遍历原始链表,根据节点值的奇偶性选择正确的链表。
```python
def split_list(head):
odd_list_head = ListNode(0)
even_list_head = ListNode(0)
current = head
while current is not None:
if current.value % 2 == 0:
current.next = even_list_head.next
even_list_head.next = current
else:
current.next = odd_list_head.next
odd_list_head.next = current
current = current.next
return odd_list_head.next, even_list_head.next
```
4. **合并链表**:
创建一个递减链表的头部`merged_list_head`,然后遍历奇数链表和偶数链表,每次从较大的链表取最小的节点插入到新链表中。
```python
def merge_lists(odd_list, even_list):
merged_list_head = ListNode(float('inf'))
odd_current = odd_list
even_current = even_list
while odd_current is not None and even_current is not None:
if odd_current.value < even_current.value:
merged_list_head.next = odd_current
odd_current = odd_current.next
else:
merged_list_head.next = even_current
even_current = even_current.next
merged_list_head = merged_list_head.next
# 如果还有剩余的链表,添加到最后
if odd_current is not None:
merged_list_head.next = odd_current
elif even_current is not None:
merged_list_head.next = even_current
return merged_list_head.next
```
5. **综合代码示例**:
```python
def main(numbers):
sorted_list = build_sorted_list(numbers)
odd_list, even_list = split_list(sorted_list)
merged_decreased_list = merge_lists(odd_list, even_list)
# 输出结果
result = []
current = merged_decreased_list
while current is not None:
result.append(current.value)
current = current.next
print("合并后的递减链表:", result)
# 示例
numbers = [1, 2, 3, 4, 5, 6]
main(numbers)
```
阅读全文