尽管使用双指针可以更容易地解决问题，但是否可以在不使用双指针的情况下从单链表中删除最后一个节点？我正在做一个简单的问题203。删除链表元素，下面是我的答案，但它未能删除最后一个节点。我不明白它为什么失败了。你能解释一下原因吗？但这里使用的类似方法似乎效果良好。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
if not head:
return head
res = head
while head:
if head.val == val and head.next:
head.val = head.next.val
head.next= head.next.next
elif head.val == val and not head.next:
head = None
else:
head = head.next
return res
input:
[1,2,6,3,4,5,6]
6
output:
[1,2,3,4,5,6]
正如另一个答案所说，最好使用sentinel节点：
class Solution:
def removeElements(self, head, val):
dummy = ListNode(-1)
dummy.next, curr = head, dummy
while curr.next:
if curr.next.val == val:
curr.next = curr.next.next
else:
curr = curr.next
return dummy.next
这里还有一个非常相似的LeetCode的解决方案：
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
sentinel = ListNode(0)
sentinel.next = head
prev, curr = sentinel, head
while curr:
if curr.val == val:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return sentinel.next
参考文献
- 有关更多详细信息，请参阅讨论板。有很多公认的解决方案，包括各种语言和解释，有效的算法，以及渐近时间/空间复杂性分析1，2
您需要专门处理叶节点。以下代码有效：
def remove_element(head, val):
if None == head:
return None
start = head
while val == start.val:
start = start.next
cur = start
while None != cur.next:
if val == cur.next.val:
if None != cur.next.next:
cur.next = cur.next.next
else:
cur.next = None
break
cur = cur.next
return head
试着使用一个假人头部
链接列表如下所示：[Dummy_head->1->2->3->4->5->6]6.next=无
我们将找到一个节点，next指向要删除的节点。
prev = dummy_head
for i in range(index): # this 'index' should be the index of the last element.
prev = dummy_head.next
ret_node = prev.next
prev.next = ret_node.next
ret_node.next_node = None # do something here to remove the element.
我试图解决Leetcode问题203。
我用java解决了它。
public ListNode removeElement(ListNode head, int val)
{
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
LinkedNode prev = dummyHead;
while(prev.next != null)
{
if(prev.next.val == val)
prev.next = prev.next.next;
else:
prev = prev.next;
}
return dummyHead.next; // "DummyHead" process shields the user.
}
您可以将其视为伪代码。