已知带头结点的双向循环链表头结点指针为list,除头结点外的每个链结点数据域值为一个整数,请写一个算法,将链表中所有数据域值大于0的结点放在所有数据域值小于0的结点之前。若链表中除头结点外没有其他结点,算法返回0,否则,算法返回1
时间: 2024-11-27 12:15:36 浏览: 18
这是一个典型的链表操作问题,可以采用迭代的方式解决。首先,我们需要两个指针分别指向头节点和当前节点,然后遍历整个链表。当遇到值大于0的节点时,我们将其移动到值小于0的节点前面。这里需要注意,由于是双向循环链表,我们需要处理边界情况以及避免形成新的环。
以下是伪代码描述:
1. 定义三个指针:prev、curr(初始指向head)、positive_head(初始指向null,用于存放所有正数节点的头节点)
2. 当curr不为空时,继续循环:
a. 检查curr的值,如果大于0且positive_head还为null,则将positive_head设置为curr,同时prev设为null
b. 如果curr值大于0,更新prev和curr,使其都指向下一个正数节点
c. 如果curr值小于0,恢复prev和curr到它们的前一个负数节点
3. 遍历结束后,如果positive_head不为null,说明有正数节点,返回1;否则,返回0
```python
def rearrange_list(head):
prev = None
curr = head
positive_head = None
while curr is not None:
if curr.val > 0 and positive_head is None:
positive_head = curr
prev = None
elif curr.val > 0:
if prev is not None:
prev.next = curr.next
curr.next.prev = prev
prev = curr
curr = curr.next
else: # curr.val <= 0
if prev is not None:
prev.next = curr
curr.prev = prev
prev = curr
curr = curr.next
if positive_head is not None:
return 1
else:
return 0
```
阅读全文