merging two sorted linked lists into one linked li

问题:

here is my code:

def merge_lists(head1, head2):
    if head1 is None and head2 is None:
        return None
    if head1 is None:
        return head2
    if head2 is None:
        return head1
    if head1.value < head2.value:
        temp = head1
    else:
        temp = head2
    while head1 != None and head2 != None:
        if head1.value < head2.value:
            temp.next = head1
            head1 = head1.next
        else:
            temp.next = head2
            head2 = head2.next
    if head1 is None:
        temp.next = head2
    else:
        temp.next = head1
    return temp
    pass

the problem here is stucked in the infinite loop.can any one tell me what the problem is

the examples are:

 assert [] == merge_lists([],[])
 assert [1,2,3] == merge_lists([1,2,3], [])
 assert [1,2,3] == merge_lists([], [1,2,3])
 assert [1,1,2,2,3,3,4,5] == merge_lists([1,2,3], [1,2,3,4,5])

回答1:

The problem with the current code is that it causes a side-effect of the temp node's next before it navigates to the next node from the current node. This is problematic when the current temp node is the current node.

That is, imagine this case:

temp = N
temp.next = N  # which means N.next = N
N = N.next     # but from above N = (N.next = N) -> N = N

There is a corrected version, with some other updates:

def merge_lists(head1, head2):
    if head1 is None:
        return head2
    if head2 is None:
        return head1

    # create dummy node to avoid additional checks in loop
    s = t = node() 
    while not (head1 is None or head2 is None):
        if head1.value < head2.value:
            # remember current low-node
            c = head1
            # follow ->next
            head1 = head1.next
        else:
            # remember current low-node
            c = head2
            # follow ->next
            head2 = head2.next

        # only mutate the node AFTER we have followed ->next
        t.next = c          
        # and make sure we also advance the temp
        t = t.next

    t.next = head1 or head2

    # return tail of dummy node
    return s.next

回答2:

Recursive algorithm for merging two sorted linked lists

def merge_lists(h1, h2):
    if h1 is None:
        return h2
    if h2 is None:
        return h1

    if (h1.value < h2.value):
        h1.next = merge_lists(h1.next, h2)
        return h1
    else:
        h2.next = merge_lists(h2.next, h1)
        return h2

回答3:

Complete code:-

Definition of "Node" class for every single node of Linked List.

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None

Definition of "linkedlist" Class.

class linkedlist:
    def __init__(self):
        self.head = None

Definition of "Merge" function.

The parameters "ll1" and "ll2" are the head of the two linked list.

def merge_lists(ll1, ll2):
    if ll1 is None:
        return ll2
    if ll2 is None:
        return ll1

    if (ll1.data < ll2.data):
        ll1.next = merge_lists(ll1.next, ll2)
        return ll1
    else:
        ll2.next = merge_lists(ll2.next, ll1)
        return ll2

Taking input into list.

l1 = []
try:
    l1 = list(map(int,input().strip().split()))
except EOFError:
    pass
l2 = []
try:
    l2 = list(map(int,input().strip().split()))
except EOFError:
    pass

Creating linked list namely ll1 and ll2 from the input list values.

ll1 = linkedlist()
ll1.head = Node(l1[0])
itr1 = ll1.head
for i in range(1,n1):
    temp = Node(l1[i])
    itr1.next = temp
    itr1 = itr1.next

ll2 = linkedlist()
ll2.head = Node(l2[0])
itr2 = ll2.head
for i in range(1,n2):
    temp = Node(l2[i])
    itr2.next = temp
    itr2 = itr2.next

Merging two sorted linked list using merge function by passing the head of the two linked list

itr = merge(ll1.head,ll2.head)

"merge" function returns an iterator itself whose values are printed as:

while itr != None:
    print(itr.data,end=" ")
    itr = itr.next

Custom input and output:-

Input

1

4

1 3 5 7

4

2 4 6 12

Output

1 2 3 4 5 6 7 12