建立一个单链表,在此链表上实现以下几种操作: 1.求此单链表的长度; 2.实现在递增整数链表插入新整数并保持序列有序性; 3.删除此单链表的第 i 个元素结点
时间: 2024-10-11 10:02:44 浏览: 26
建立单链表并实现所需操作:
1. **求链表长度**:
在Python中,你可以通过遍历整个链表并在遇到`None`时计数节点的数量来计算单链表的长度。示例如下:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def get_length(head):
count = 0
current = head
while current:
count += 1
current = current.next
return count
```
2. **在递增整数链表中插入新整数并保持有序**:
可以先比较新值和当前节点的值,然后插入到适当的位置。如果新值小于当前节点,就继续向前移动直到找到合适位置。插入节点时,需要更新前一个节点的`next`指针指向新插入的节点。
```python
def insert_sorted(head, value):
new_node = ListNode(value)
if not head or head.val > value:
new_node.next = head
head = new_node
else:
current = head
while current.next and current.next.val < value:
current = current.next
new_node.next = current.next
current.next = new_node
return head
```
3. **删除链表的第 i 个元素节点**:
需要处理特殊情况,如 i 小于 1 或者 i 越界。可以通过两个指针,快指针每次走两步,慢指针每次走一步,当快指针到达第 i+1 个节点时,慢指针刚好在第 i 个节点,将快指针后面的节点接到慢指针前面即可。
```python
def remove_nth_from_end(head, n):
dummy = ListNode(0) # 创建虚拟头节点
dummy.next = head
slow = fast = dummy
# Move fast pointer n nodes ahead
for _ in range(n + 1):
if fast is None:
break
fast = fast.next
# Now fast points to the node after nth from end
if fast is None:
# If n is greater than list length, delete first element
head = head.next
else:
# Move both pointers until they meet (fast will be at end)
while fast.next is not None:
fast = fast.next
slow = slow.next
# Remove the node pointed by slow and adjust pointers
slow.next = slow.next.next
return dummy.next
```
阅读全文