2.有一个整数单链表表L,设计一个尽可能高效的算法将所 有负整数的元素移到其它元素的前面。
时间: 2024-06-15 17:05:32 浏览: 14
要将所有负整数的元素移到其他元素的前面,可以使用两个指针来实现。一个指针用于遍历链表,另一个指针用于记录当前位置。
具体算法如下:
1. 初始化两个指针,一个指向链表的头节点,另一个指向链表的第一个非负整数节点(初始时可以指向空节点)。
2. 遍历链表,对于每个节点:
- 如果节点的值为负整数,将其移到第一个非负整数节点之前,并更新第一个非负整数节点的位置。
- 如果节点的值为非负整数,继续遍历下一个节点。
3. 遍历完成后,所有负整数的元素都会被移到第一个非负整数节点之前。
以下是算法的示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def moveNegativeElements(head):
if not head or not head.next:
return head
dummy = ListNode(0) # 创建一个虚拟头节点
dummy.next = head
prev_positive = dummy # 记录第一个非负整数节点的位置
curr = head
while curr:
if curr.val < 0:
# 将当前节点移到第一个非负整数节点之前
prev_positive.next = curr.next
curr.next = dummy.next
dummy.next = curr
curr = prev_positive.next
else:
prev_positive = curr
curr = curr.next
return dummy.next
```