#### Determine if the two linked lists intersect

http://www.knowsh.com

Given two singly linked list, determine if the two lists intersect. Return the intersecting node. Note that the intersection is defined based on reference, not value. 38 more words

Steve discusses problems with Mind Mapping and an improved linked list approach to grappling with complex scenarios.

Podcast

(Source code for Linked List can be found here –> Linked List)

Linked List is a list of elements/whatever you say which are of two kinds: 1,067 more words

Data Structure

#### CIE Computer Science Linked List Code

*** This is a slightly modified python code from the Cambridge coursebook as the pseudo code provided by the book does not work ***

``````class ListNode:
def __init__(self): # object for each node
self.Data = 0
self.Pointer = 0

def __init__(self,n): # initialisation
self.__NULLPOINTER = -1
self.__StartPointer = self.__NULLPOINTER
self.__FreeListPointer = 0
self.List = []
for i in range(n):
self.List.append(ListNode())
self.List[i].Pointer = i+1
self.List.Pointer = self.__NULLPOINTER

def display(self): # print a display in order of index position
print("Start Pointer:", self.__StartPointer)
print("Free List Pointer:", self.__FreeListPointer)
print("|{0:^5}|{1:^10}|{2:^10}|".format("Pos", "Data", "Pointer"))
for i in range(len(self.List)):
print("|{0:^5}|{1:^10}|{2:^10}|".format(i, self.List[i].Data, self.List[i].Pointer))

def insert(self,item): # insert item, returns True when inserted and False when set is full
if self.__FreeListPointer != self.__NULLPOINTER:
NewNodePointer = self.__FreeListPointer
self.List.Data = item
self.__FreeListPointer = self.List.Pointer
PreviousPointer = self.__StartPointer
ThisPointer = self.__StartPointer
if self.__StartPointer == self.__NULLPOINTER or item < self.List.Data:
ThisPointer = self.__StartPointer
self.List.Pointer = ThisPointer
self.__StartPointer = NewNodePointer
else:
HasRun = False
while self.List.Data < item and ThisPointer != self.__NULLPOINTER:
PreviousPointer = ThisPointer
ThisPointer = self.List.Pointer
HasRun = True
if HasRun:
self.List.Pointer = self.List.Pointer
self.List.Pointer = NewNodePointer
return True
else:
return False

def delete(self, item): # delete an item, returns True when deleted and False when not found or set empty
if self.__StartPointer == self.__NULLPOINTER:
return False
if self.List.Data == item:
self.List.Data = 0
temp = self.List.Pointer
self.List.Pointer = self.__FreeListPointer
self.__FreeListPointer = self.__StartPointer
self.__StartPointer = temp
else:
CurrentNodePtr = self.__StartPointer
PreviousPtr = -1
while CurrentNodePtr != self.__NULLPOINTER and self.List.Data != item:
PreviousPtr = CurrentNodePtr
CurrentNodePtr = self.List.Pointer
if CurrentNodePtr == self.__NULLPOINTER and self.List.Data != item:
return False
self.List.Pointer = self.List.Pointer
self.List.Data = 0
self.List.Pointer = self.__FreeListPointer
self.__FreeListPointer = CurrentNodePtr
return True

def find(self, item): # return position of an item, -1 if not found
CurrentNodePtr = self.__StartPointer
while CurrentNodePtr != self.__NULLPOINTER and self.List.Data != item:
CurrentNodePtr = self.List.Pointer
return CurrentNodePtr

def access(self): # print a display in order of pointers
CurrentNodePtr = self.__StartPointer
print("|{0:^10}|{1:^5}|".format("Data","Pos"))
while CurrentNodePtr != self.__NULLPOINTER:
print("|{0:^10}|{1:^5}|".format(self.List.Data, self.List.index(self.List)))
CurrentNodePtr = self.List.Pointer

########################
### Example Commands ###
########################

A Level