Write a function link_to_list that takes in a linked list and returns the sequence as a Python list. You may assume that the input list is shallow; none of the elements is another linked list. Try to find both an iterative and recursive solution for this problem!
时间: 2024-02-29 20:53:31 浏览: 29
Sure! Here are iterative and recursive implementations of the `link_to_list` function:
Iterative Solution:
```python
def link_to_list(head):
result = []
current = head
while current is not None:
result.append(current.val)
current = current.next
return result
```
Recursive Solution:
```python
def link_to_list(head):
if head is None:
return []
return [head.val] + link_to_list(head.next)
```
In the recursive solution, we first check if the current node is None, in which case we return an empty list. Otherwise, we return a list that contains the value of the current node and the result of calling the function recursively on the next node.
相关问题
Implement the function that searches a given value x in linked list headed with node nil.
Sure, here's an implementation of the function in Python:
```
class Node:
def __init__(self, value):
self.value = value
self.next = None
def search_linked_list(nil, x):
node = nil.next
while node is not None:
if node.value == x:
return node
node = node.next
return None
```
Here, `nil` is the head of the linked list, which is typically a dummy node with no value that serves as a placeholder. The `search_linked_list` function takes in `nil` and the value `x` to search for, and returns the node in the linked list that contains `x`, or `None` if `x` is not found.
The function works by starting at the first node after `nil`, and iterating through the linked list until it finds the node with the value `x`. If it traverses the entire linked list without finding `x`, it returns `None`.
Note that this implementation assumes that the values in the linked list are unique. If there can be multiple nodes with the same value, you may need to modify the function to return a list of nodes instead of just one.
write a nonrecursive procedure to reverse a singly linked list in o(n) time using constant extra space.
使用常数额外空间,在O(n)时间内编写一个非递归程序来反转一个单向链表。
可以使用三个指针:prev,curr和next。prev指向当前节点的前一个节点,curr指向当前节点,next指向当前节点的下一个节点。在遍历链表时,将curr的next指向prev,然后将prev和curr向前移动一个节点,直到curr到达链表末尾。最后,将链表的头节点指向prev,即可完成反转。