设计一个算法,将一个结点值为自然数的单链表拆分成两个单链表,原表中保留值为偶数的结点,而值为奇数的结点按它们在原表的相对次序组成一个新的单链表数据结构
时间: 2024-05-11 10:19:49 浏览: 93
数据结构课程设计--单链表两个集合相加减的算法.doc
可以按照以下步骤设计算法:
1. 定义两个新的链表,一个用于存储偶数结点,一个用于存储奇数结点。
2. 遍历原始链表的每个结点,判断其值的奇偶性。
3. 如果结点的值为偶数,则将其从原始链表中删除,并将其插入到偶数链表的末尾。
4. 如果结点的值为奇数,则将其从原始链表中删除,并将其插入到奇数链表的末尾。
5. 遍历完成后,原始链表中只剩下偶数结点,奇数结点已经被挪到了新的奇数链表中。
6. 返回两个链表,一个是偶数链表,一个是奇数链表。
以下是Python实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def split_list(head: ListNode) -> (ListNode, ListNode):
even_head = even_tail = ListNode()
odd_head = odd_tail = ListNode()
while head:
if head.val % 2 == 0:
even_tail.next = head
even_tail = even_tail.next
else:
odd_tail.next = head
odd_tail = odd_tail.next
head = head.next
even_tail.next = None
odd_tail.next = None
return even_head.next, odd_head.next
```
其中,even_head和odd_head是两个空节点,用于方便操作。遍历完成后,需要将偶数链表和奇数链表的结尾节点的next指针设置为None,以避免出现环。
阅读全文