Interview Questions
function Node(data, next) { this.data = data; this.next = next; }
class Node: def __init__(self, data, next): self.data = data self.next = nextThis is how we can then create a linked list with connecting nodes:
var n1 = new Node("Hello", null); var n2 = new Node("21", n1); var n3 = new Node("Green", n2); // assign a node to the head which functions // as the entry into our linked list var head = n3;
n1 = Node("Hello", None) n2 = Node("21", n1) n3 = Node("Green", n2) # assign a node to the head which functions # as the entry into our linked list head = n3Our challenge is to now find the middle node in a linked list. We don't initially know the length of a linked list, all we have is a single node which acts as the head of the linked list and which we can access all other nodes by traversing through each nodes "next" property. We can continuously loop through each node until we get to a node that has a "next" property of null, which means we have reached the last node.
function Node(data, next) { this.data = data; this.next = next; } // setup some nodes and connect them to each other // the linked list looks like: // (head) n5 -> n4 -> n3 -> n2 -> n1 -> null var n1 = new Node("Hello", null); var n2 = new Node("21", n1); var n3 = new Node("Green", n2); var n4 = new Node("Blue", n3); var n5 = new Node("Daniel", n4); // assign a node to the head which functions // as the entry into our linked list var head = n5; // setup pointers to both start // at the head of the linked list var fastPointer = head; var slowPointer = head; // loop through the linked list // when fastPointer reaches the end of the list // then slowPointer will be at the middle node while (fastPointer.next !== null && fastPointer.next.next !== null) { fastPointer = fastPointer.next.next; slowPointer = slowPointer.next; } // slowPointer is now at the middle node in the linked list slowPointer.data
class Node: def __init__(self, data, next): self.data = data self.next = next # setup some nodes and connect them to each other # the linked list looks like: # (head) n5 -> n4 -> n3 -> n2 -> n1 -> None n1 = Node("Hello", None) n2 = Node("21", n1) n3 = Node("Green", n2) n4 = Node("Blue", n3) n5 = Node("Daniel", n4) # assign a node to the head which functions # as the entry into our linked list head = n5 # setup pointers to both start # at the head of the linked list fastPointer = head slowPointer = head # loop through the linked list # when fastPointer reaches the end of the list # then slowPointer will be at the middle node while fastPointer.next != None and fastPointer.next.next != None: fastPointer = fastPointer.next.next slowPointer = slowPointer.next # slowPointer is now at the middle node in the linked list print slowPointer.data
kaizen
commented on 06/26/16
arknamal
commented on 08/09/18
mrj936
commented on 09/15/18
yossarian21
commented on 10/08/18
mrj936
commented on 09/15/18
aleaallee
commented on 01/19/19
class Node: def __init__(self, data, next): self.data=data self.next=next n1 = Node("Hello ,", None) n2 = Node("World, ", n1) n3 = Node("Gray", n2) head = n3 fastPointer=head slowPointer=head while fastPointer.next !=None and fastPointer ==None: fastPointer=fastPointer.next slowPointer=slowPointer.next print(slowPointer.data)
Garywei
commented on 09/04/18