I am trying to remove the kth element from the END of a linked list. Here is my code
class LinkedList:
def __init__(self, value):
self.value = value
self.next = None
def removeKthNodeFromEnd(head, k):
if k == 0 or head is None:
return
temp = head
while temp is not None and k > 1:
temp = temp.next
k -= 1
if temp is None or k > 1:
return head
trailing = None
leading = head
while temp.next is not None:
trailing = leading
leading = leading.next
temp = temp.next
if trailing is None:
head = head.next
else:
trailing.next = leading.next
head = LinkedList(0)
head.next = LinkedList(1)
head.next.next = LinkedList(2)
head.next.next.next = LinkedList(3)
head.next.next.next.next = LinkedList(4)
head.next.next.next.next.next = LinkedList(5)
head.next.next.next.next.next.next = LinkedList(6)
head.next.next.next.next.next.next.next = LinkedList(7)
head.next.next.next.next.next.next.next.next = LinkedList(8)
head.next.next.next.next.next.next.next.next.next = LinkedList(9)
removeKthNodeFromEnd(head, 10)
while head is not None:
print(head.value)
head = head.next
But this does not work and prints out all the values in the linked list from 0 to 9. Why is this the case? If the node to delete is the head node which I check by checking trailing is None, then I update head = head.next. I am changing head to be the next node. I can return head after this update and the result of head = removeKthNodeFromEnd(head, k) will give me the desired output but why can't I do it the other way without returning anything? For instance in my solution I can get rid of any element in between the first and last node including the last and works just fine. The original head gets updated and node gets removed. But when trying to update the head node head = head.next it does not work.
One way I achieved this is by doing the following...
if trailing is None:
head.value = head.next.value
head.next = head.next.next
But why must I use the values? To me this seems the same as
if trailing is None:
head = head.next
head.next = head.next.next
but does not work
CodePudding user response：
Consider utilizing a dummy node to simplify your logic:
from typing import Optional
class LinkedList:
def __init__(self, value: int):
self.value = value
self.next = None
def __iter__(self):
return LinkedListIterator(self)
class LinkedListIterator:
def __init__(self, head: LinkedList):
self.curr = head
def __iter__(self):
return self
def __next__(self):
if not self.curr:
raise StopIteration
else:
value = self.curr.value
self.curr = self.curr.next
return f'[{value}]'
def remove_kth_node_from_end(head: Optional[LinkedList],
k: int) -> Optional[LinkedList]:
"""Removes the kth node end of the passed in LinkedList."""
dummy = trailing = leading = LinkedList(0)
dummy.next = head
for _ in range(k):
leading = leading.next
while leading and leading.next:
leading = leading.next
trailing = trailing.next
trailing.next = trailing.next.next
return dummy.next
def main() -> None:
head = LinkedList(0)
head.next = LinkedList(1)
head.next.next = LinkedList(2)
head.next.next.next = LinkedList(3)
head.next.next.next.next = LinkedList(4)
head.next.next.next.next.next = LinkedList(5)
head.next.next.next.next.next.next = LinkedList(6)
head.next.next.next.next.next.next.next = LinkedList(7)
head.next.next.next.next.next.next.next.next = LinkedList(8)
head.next.next.next.next.next.next.next.next.next = LinkedList(9)
k = 3
print(f'{k = }')
print('Before removing kth node from end:')
print('->'.join(head))
new_head = remove_kth_node_from_end(head, k)
print('After removing kth node from end:')
print('->'.join(new_head))
if __name__ == '__main__':
main()
Output:
k = 3
Before removing kth node from end:
[0]->[1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]
After removing kth node from end:
[0]->[1]->[2]->[3]->[4]->[5]->[6]->[8]->[9]
CodePudding user response：
It doesn't work because head in that function is a local name. Assigning to a local variable never does anything to other variables, even not when they happen to have the same name (like the global head).
The "trick" you have by moving a linked list value with head.value = head.next.value will not work when the list only has one node.
One way to do this, is to return the (potentially modified) value of head, and expect the caller to assign this back to their own head variable.
So:
in
removeKthNodeFromEndmake sure allreturnstatements toreturn head, and that you add areturn headat the very end. In short,removeKthNodeFromEndshould always returnhead.in the main program, change the call to
head = removeKthNodeFromEnd(head, 10)
That will solve your issue.
Here are some ideas to make your code more elegant:
- Create a separate class for maintaining the head of the linked list
- Improve the constructor, so that it is easier to initialise a linked list
- Add an iterator so it is easier to print a linked list
class Node: # renamed
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt # is now an argument
class LinkedList: # added
def __init__(self, *values):
self.head = None
if values: # populate the list with values
for value in reversed(values):
self.push_front(value)
def push_front(self, value):
self.head = Node(value, self.head)
def __iter__(self):
node = self.head
while node:
yield node.value
node = node.next
def removeKthNodeFromEnd(self, k):
if k <= 0:
return
temp = self.head
for _ in range(k):
if not temp: # k is out of range
return
temp = temp.next
if temp:
trailing = self.head
while temp.next:
trailing = trailing.next
temp = temp.next
trailing.next = trailing.next.next
else:
self.head = self.head.next
lst = LinkedList(*range(10))
print(*lst)
lst.removeKthNodeFromEnd(0)
print(*lst)