Confused with Linked List Pointers and how it changes the original linked list

Question

I am studying Data Structures and Algorithms. I encountered some confusion below.

from typing import *

class Node:
    curr_node_value: Any
    next_node: Node
    def __init__(self, curr_node_value: Any = None):
        # a node can hold a current value and by default its next node is None
        # however we can assign values to the next of a node, but the next must be of object node as denoted
        # note the distinction between curr node value and next node, they are diff
        self.curr_node_value = curr_node_value
        self.next_node = None
        
class LinkedList:
    def __init__(self):
        # key point is that end of every llist, it points to None always
        self.head = None
        
        
ll1_first = Node(1)
ll1_second = Node(2)
ll1_third = Node(4)

ll2_first = Node(1)
ll2_second = Node(3)
ll2_third = Node(4)

# create llist 1
ll1 = LinkedList()
ll1.head = ll1_first
ll1.head.next_node = ll1_second
ll1.head.next_node.next_node = ll1_third

# create llist 2
ll2 = LinkedList()
ll2.head = ll2_first
ll2.head.next_node = ll2_second
ll2.head.next_node.next_node = ll2_third


merged_sorted_llist = LinkedList()

ll1_temp_curr_node = ll1.head
ll2_temp_curr_node = ll2.head

while ll1_temp_curr_node is not None and ll2_temp_curr_node is not None:
    print(ll1_temp_curr_node.curr_node_value)
    ll1_curr_node = ll1_temp_curr_node
    ll2_curr_node = ll2_temp_curr_node
 
    if ll1_curr_node.curr_node_value <= ll2_curr_node.curr_node_value:
        merged_sorted_llist.head = ll1_curr_node
        #print(merged_sorted_llist.head.next_node.curr_node_value)
        merged_sorted_llist.head.next_node = ll2_curr_node
 

    ll1_temp_curr_node = ll1_temp_curr_node.next_node
    ll2_temp_curr_node = ll2_temp_curr_node.next_node

The code is a subset of a larger question but I cannot understand clearly why when you print print(ll1_temp_curr_node.curr_node_value) it gives you 1, 1, 3 instead of 1, 2, 4. I did extensive debugging and if you comment out merged_sorted_llist.head.next_node = ll2_curr_node it will print out 1, 2, 4.

After googling, I came to read this post and believe I messed up somewhere in variable assigning, especially if I set the attributes. It is still not very obvious to me where.

Devesh · Accepted Answer · 2022-03-19 09:04:16Z

2

I can see two problems:

You don't want to update the merged list's head in each iteration
Once you assign the head of the merged list, you still need to find the next node by comparing two candidate nodes (one from each list)

Here is my implementation for this problem:

# Linked List Node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
  
  
# Create & Handle List operations
class LinkedList:
    def __init__(self):
        self.head = None
  
    # Method to display the list
    def printList(self):
        temp = self.head
        while temp:
            print(temp.data, end=" ")
            temp = temp.next
    
    
  
    # Method to add element to list
    def addToList(self, newData):
        newNode = Node(newData)
        if self.head is None:
            self.head = newNode
            return
  
        last = self.head
        while last.next:
            last = last.next
  
        last.next = newNode

# Create 2 lists
listA = LinkedList()
listB = LinkedList()
  
# Add elements to the list in sorted order
listA.addToList(5)
listA.addToList(10)
listA.addToList(15)
  
listB.addToList(2)
listB.addToList(3)
listB.addToList(20)

def mergeLists(h1, h2):
    merged_head = None
    
    if h1 is None:
        return h2
    
    if h2 is None:
        return h1
    
    if h1.data > h2.data:
        merged_head = h2
        merged_head.next = mergeLists(h1, h2.next)
    else:
        merged_head = h1
        merged_head.next = mergeLists(h1.next, h2)

    return merged_head

res = LinkedList()
res.head = mergeLists(listA.head, listB.head)

answered Mar 19, 2022 at 9:04

Devesh

6134 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ilovewt Over a year ago

I think this does not answer my question, I have no issue doing up the problem, I have an issue of understanding the "bug" in my code.

trincot Over a year ago

@ilovewt, Devesh has well explained at the start of their answer what the problem is in your code. It cannot be right to set the head of your merged list in each iteration. Think about it. It is the cause of the output you get.

Collectives™ on Stack Overflow

Confused with Linked List Pointers and how it changes the original linked list

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related