Archive

Tag Archives: linked

Question

How do you remove a node from a singly linked list, given only that node? Head node is not given.

Solution

Set next of this node to the next of the next node.

node->next = node->next->next;

Reference

Glassdoor

Question

Reverse a linked list.

Sample

# node structure
class Node:
    value = None
    next = None

    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

# reverse the linked list and return the head node
def reverse_linked_list(head):
    reversed_head = None
    last_node = None
    node = head
    while node:
        next_node = node.next
        if next_node is None: reversed_head = node
        node.next = last_node
        last_node = node
        node = next_node
    return reversed_head

# linked list
node_9 = Node(9)
node_8 = Node(8, node_9)
node_7 = Node(7, node_8)
node_6 = Node(6, node_7)
node_5 = Node(5, node_6)
node_4 = Node(4, node_5)
node_3 = Node(3, node_4)
node_2 = Node(2, node_3)
node_1 = Node(1, node_2)
node_head = node_1

# testing
node_reversed_head = reverse_linked_list(node_head)
node_temp = node_reversed_head
while node_temp:
    print node_temp.value,
    node_temp = node_temp.next

Question

Write an algorithm to remove duplicated node from a linked list.

Solution

There are many ways to do it. For the first one, as the simplest one, we could use 2 loops to compare each element with all other elements. However, this takes forever: O(n²).

The second way

Reference

http://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/

Question

Validate a linked list whether there is a loop in it. That is, there is a node in a linked list with  the next pointer pointing to a node ahead in the same linked list. This is the question I encountered in 2013 spring, from a Yahoo phone interview.

Solution

Define 2 pointers pointing to the head of the linked list. Then we move the pointers at different speed. For example, move 1 step for pointer 1 every time, but 2 steps for pointer 2. Test to see if they point to the same element. If so we got a loop. If not, repeat until you find a loop or you reach the end of the list.

loop
    slow = slow->next
    fast = fast->next->next

Question

Given a linked list, find the Kth last node in a linked list. The last 0th node is the tail node in the linked list.

Solution

Easy task. Construct 2 pointers: P1 and P2. First, both of them are set to head. Move P2 to the next Kth node.

Example

# node structure
class node:
    data = None
    next = None
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

# get item
def get_item(head, k):
    pointer_1 = head
    pointer_2 = head
    for i in xrange(k+1):
        if pointer_2 is not None:
            pointer_2 = pointer_2.next
    while pointer_2 is not None:
        pointer_1 = pointer_1.next
        pointer_2 = pointer_2.next
    return pointer_1

# linked list
node_9 = node(9)
node_8 = node(8, node_9)
node_7 = node(7, node_8)
node_6 = node(6, node_7)
node_5 = node(5, node_6)
node_4 = node(4, node_5)
node_3 = node(3, node_4)
node_2 = node(2, node_3)
node_1 = node(1, node_2)

# main
head = node_1
print get_item(head, 0).data
print get_item(head, 9).data
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

struct ListNode
{
    char data;
    ListNode* next;
};
ListNode* head,*p,*q;
ListNode *pone,*ptwo;

ListNode* fun(ListNode *head,int k)
{
    pone = ptwo = head;
    for(int i=0;i<=k-1;i++)
        ptwo=ptwo->next;
    while(ptwo!=NULL)
    {
        pone=pone->next;
        ptwo=ptwo->next;
    }
    return pone;
}

int main()
{
    char c;
    head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    p = head;
    while(c !='0')
    {
        q = (ListNode*)malloc(sizeof(ListNode));
        q->data = c;
        q->next = NULL;
        p->next = q;
        p = p->next;
        c = getchar();
    }
    cout<<"---------------"<<endl;
    cout<<fun(head,2)->data<<endl;

    return 0;
}

/////////////////////////////
1254863210
---------------
2
Press any key to continue
////////////////////////////

9Question

Get the greatest distance between two nodes in a binary tree. Assume links between nodes are bidirectional. Distance is defined as the amount of nodes connected along the path linked two nodes. Write an algorithm to calculate distance between two nodes. Take the figure at the right, the greatest length should be 4.

Solution

Usual post-order recursive binary tree traversal should do the job. In this case, (obviously) the path must passes through the root. So we should do the following. Recursively return the max length (from left or right) to the parent, and make an exception for the root. The result is simply the sum of maxes from left and right.

Example

# node structure
class bst_node:
    left = None
    right = None
    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

# join left and right max at root, literally
def get_max_len(root):
    left_max = depth_first_traversal(root.left)
    right_max = depth_first_traversal(root.right)
    return left_max + right_max

# a usual traversal, returning the max length begin
# from this node
def depth_first_traversal(node):
    if not node: return 0
    left_max = depth_first_traversal(node.left)
    right_max = depth_first_traversal(node.right)
    return max(left_max, right_max) + 1

# binary tree setup
node_12 = bst_node()
node_13 = bst_node()
node_05 = bst_node()
node_07 = bst_node(node_12, node_13)
node_09 = bst_node()
node_11 = bst_node()
node_06 = bst_node(node_05, node_07)
node_10 = bst_node(node_09, node_11)
node_08 = bst_node(node_06, node_10)

# answer should be 5
root = node_08
print get_max_len(root)
# node structure
class bst_node:
    left = None
    right = None
    left_max_dist = 0
    right_max_dist = 0

    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

    def max_dist(self):
        return max(self.left_max_dist, self.right_max_dist)

# calculate function
def calculate_max_len(node):

    # check node
    if not node: return 0

    # if left is not empty, then left is is the max + 1
    if node.left:
        calculate_max_len(node.left)
        node.left_max_dist = node.left.max_dist() + 1

    # if right is not empty, right is is the max + 1
    if node.right:
        calculate_max_len(node.right)
        node.right_max_dist = node.right.max_dist() + 1

    # return the max dist
    return node.left_max_dist + node.right_max_dist

# bst
node_12 = bst_node()
node_13 = bst_node()
node_5 = bst_node()
node_7 = bst_node(node_12, node_13)
node_9 = bst_node()
node_11 = bst_node()
node_6 = bst_node(node_5, node_7)
node_10 = bst_node(node_9, node_11)
node_8 = bst_node(node_6, node_10)

# answer should be 5
root = node_8
print calculate_max_len(root)
// 数据结构定义
struct NODE
{
     NODE* pLeft;            // 左子树
     NODE* pRight;          // 右子树
     int nMaxLeft;          // 左子树中的最长距离
     int nMaxRight;         // 右子树中的最长距离
     char chValue;        // 该节点的值
};

int nMaxLen = 0;

// 寻找树中最长的两段距离
void FindMaxLen(NODE* pRoot)
{
     // 遍历到叶子节点,返回
     if(pRoot == NULL) {
          return;
     }
     // 如果左子树为空,那么该节点的左边最长距离为0
     if(pRoot -> pLeft == NULL) {
          pRoot -> nMaxLeft = 0;
     }
     // 如果右子树为空,那么该节点的右边最长距离为0
     if(pRoot -> pRight == NULL) {
          pRoot -> nMaxRight = 0;
     }
     // 如果左子树不为空,递归寻找左子树最长距离
     if(pRoot -> pLeft != NULL) {
          FindMaxLen(pRoot -> pLeft);
     }
     // 如果右子树不为空,递归寻找右子树最长距离
     if(pRoot -> pRight != NULL) {
          FindMaxLen(pRoot -> pRight);
     }
     // 计算左子树最长节点距离
     if(pRoot -> pLeft != NULL) {
          int nTempMax = 0;
          if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight) {
               nTempMax = pRoot -> pLeft -> nMaxLeft;
          }
          else {
               nTempMax = pRoot -> pLeft -> nMaxRight;
          }
          pRoot -> nMaxLeft = nTempMax + 1;
     }
     // 计算右子树最长节点距离
     if(pRoot -> pRight != NULL) {
          int nTempMax = 0;
          if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight) {
               nTempMax = pRoot -> pRight -> nMaxLeft;
          }
          else {
               nTempMax = pRoot -> pRight -> nMaxRight;
          }
          pRoot -> nMaxRight = nTempMax + 1;
     }
     // 更新最长距离
     if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen) {
          nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
     }
 }
 //很明显,思路完全一样,但书上给的这段代码更规范!:)。
//定义一个结构体
struct NODE
{
    NODE* pLeft;
    NODE* pRight;
    int MaxLen;
    int MaxRgt;
};
NODE* pRoot;  //根节点
int MaxLength;

void traversal_MaxLen(NODE* pRoot) {
    if(pRoot == NULL) {
        return 0;
    };
    if(pRoot->pLeft == NULL) {
        pRoot->MaxLeft = 0;
    }
    // 若左子树不为空
    else {
        int TempLen = 0;
        // 左子树上的,某一节点,往左边大,还是往右边大
        if(pRoot->pLeft->MaxLeft > pRoot->pLeft->MaxRight) {
            TempLen+=pRoot->pLeft->MaxLeft;
        }
        else {
            TempLen+=pRoot->pLeft->MaxRight;
        }
        pRoot->nMaxLeft = TempLen + 1;
        traversal_MaxLen(NODE* pRoot->pLeft); // 此处,加上递归
    }

    if(pRoot->pRigth == NULL) {
        pRoot->MaxRight = 0;
    }
    // 若右子树不为空
    else {
        int TempLen = 0;
        // 右子树上的,某一节点,往左边大,还是往右边大
        if(pRoot->pRight->MaxLeft > pRoot->pRight->MaxRight) {
            TempLen+=pRoot->pRight->MaxLeft;
        }
        else {
            TempLen+=pRoot->pRight->MaxRight;
        }
        pRoot->MaxRight = TempLen + 1;
        traversal_MaxLen(NODE* pRoot->pRight); // 此处,加上递归
    }

    if(pRoot->MaxLeft + pRoot->MaxRight > 0) {
        MaxLength=pRoot->nMaxLeft + pRoot->MaxRight;
    }
}

Question

Given 2 linked list head pointers, determine whether they intersect at some point.

Solution

First of all, linked list can have loop or not, and this gives 3 possible situations.

1. For the 2 loops head pointer 1 and head pointer 2, move pointer 1 at normal speed, and pointer 2 at double speed. If they intersect, node will be the same at some point. Otherwise infinity loop occurs. (need to be fixed)

2. For 2 straight linked list, they would have the same tails if they intersect.

3. For a loop and a straight list, use the first algorithm and let the loop to move at double speed. If they don’t intersect, tail of the straight list will end the checking.

So one of the key idea is to check if a linked list is loop. Since loop may start not at the head, we can not use head pointer as the checking reference. We could instead use the algorithm 1 against itself, if it has loop the 2 moving pointer will meet at some point.

Sample Code

# node structure
class Node:
    value = None
    next = None

    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

# check if the list has loop
def is_loop(head):
    if not head: return False
    slow_trace = fast_tract = head
    while fast_tract and fast_tract.next:
        slow_trace = slow_trace.next
        fast_tract = fast_tract.next.next
        if slow_trace == fast_tract: return True
    return False

# check meet up if list is loop
def check_meet_up_with_loop(head_1, head_2):
    # todo: infinite loop if not meeting up
    while head_1 != head_2 and head_1 and head_2:
        head_1 = head_1.next
        head_2 = head_2.next
        if head_2.next: head_2 = head_2.next
    return head_1 == head_2 and head_1 is not None and head_2 is not None

# check meet up if list is not loop
def check_meet_up_without_loop(head_1, head_2):
    tail_1 = head_1
    tail_2 = head_2
    while tail_1.next: tail_1 = tail_1.next
    while tail_2.next: tail_2 = tail_2.next
    return tail_1 == tail_2

# list 1
node_9 = Node(9)
node_8 = Node(8, node_9)  # meet of list 1 and 2
node_7 = Node(7, node_8)
node_6 = Node(6, node_7)
node_5 = Node(5, node_6)
head_1 = node_5
print is_loop(head_1) == False

# list 2, will meet with list 1
node_4 = Node(4, node_8)
node_3 = Node(3, node_4)
node_2 = Node(2, node_3)
head_2 = node_2
print is_loop(head_2) == False

# list 3, separate list
node_1 = Node(1)
node_0 = Node(0, node_1)
head_3 = node_0
print is_loop(head_3) == False

# list 4 with loop
node_15 = Node(15)
node_14 = Node(14, node_15)
node_13 = Node(13, node_14)
node_12 = Node(12, node_13)
node_11 = Node(11, node_12)
node_15.next = node_11
head_4 = node_11
print is_loop(head_4)  # true

# list 5 same loop with 4
node_25 = Node(25, node_14)
node_24 = Node(24, node_25)
head_5 = node_24
print is_loop(head_5)  # true

# list 6, separate loop
node_35 = Node(35)
node_34 = Node(34, node_35)
node_35.next = node_34
head_6 = node_34
print is_loop(head_6)  # true

# checking
print
print check_meet_up_without_loop(head_1, head_2) == True
print check_meet_up_without_loop(head_1, head_3) == False
print check_meet_up_with_loop(head_4, head_5) == True
print check_meet_up_with_loop(head_4, head_6) == False
#include <iostream>

// node structure
struct Node
{
	int value;
	Node *next;

	Node(int value, Node *next = NULL)
	{
		this->value = value;
		this->next = next;
	}
};

// check if the list has loop
bool is_loop(Node *head)
{
	if (!head) return false;
	Node *slow_trace = head;
	Node *fast_tract = head;
	while (fast_tract && fast_tract->next) {
		slow_trace = slow_trace->next;
		fast_tract = fast_tract->next->next;
		if (slow_trace == fast_tract) return true;
	}
	return false;
}

// check meet up if list is loop
bool check_meet_up_with_loop(Node *head_1, Node *head_2)
{
	// todo: infinite loop if not meeting up
	while (head_1 != head_2 && head_1 && head_2) {
		head_1 = head_1->next;
		head_2 = head_2->next;
		if (head_2->next) head_2 = head_2->next;
	}
	return head_1 == head_2 && head_1 && head_2;
}

// check meet up if list is not loop
bool check_meet_up_without_loop(Node *head_1, Node *head_2)
{
	Node *tail_1 = head_1;
	Node *tail_2 = head_2;
	while (tail_1->next) tail_1 = tail_1->next;
	while (tail_2->next) tail_2 = tail_2->next;
	return tail_1 == tail_2;
}

int main()
{
	// list 1
	Node *node_9 = new Node(9);
	Node *node_8 = new Node(8, node_9);  // meet of list 1 and 2
	Node *node_7 = new Node(7, node_8);
	Node *node_6 = new Node(6, node_7);
	Node *node_5 = new Node(5, node_6);
	Node *head_1 = node_5;
	printf("%sn", is_loop(head_1) == false ? "true" : "false");

	// list 2, will meet with list 1
	Node *node_4 = new Node(4, node_8);
	Node *node_3 = new Node(3, node_4);
	Node *node_2 = new Node(2, node_3);
	Node *head_2 = node_2;
	printf("%sn", is_loop(head_2) == false ? "true" : "false");

	// list 3, separate list
	Node *node_1 = new Node(1);
	Node *node_0 = new Node(0, node_1);
	Node *head_3 = node_0;
	printf("%sn", is_loop(head_3) == false ? "true" : "false");

	// list 4 with loop
	Node *node_15 = new Node(15);
	Node *node_14 = new Node(14, node_15);
	Node *node_13 = new Node(13, node_14);
	Node *node_12 = new Node(12, node_13);
	Node *node_11 = new Node(11, node_12);
	node_15->next = node_11;
	Node *head_4 = node_11;
	printf("%sn", is_loop(head_4) ? "true" : "false");  // true

	// list 5 same loop with 4
	Node *node_25 = new Node(25, node_14);
	Node *node_24 = new Node(24, node_25);
	Node *head_5 = node_24;
	printf("%sn", is_loop(head_5) ? "true" : "false");  // true

	// list 6, separate loop
	Node *node_35 = new Node(35);
	Node *node_34 = new Node(34, node_35);
	node_35->next = node_34;
	Node *head_6 = node_34;
	printf("%sn", is_loop(head_6) ? "true" : "false");  // true

	// checking
	printf("%sn", check_meet_up_without_loop(head_1, head_2) == true ? "true" : "false");
	printf("%sn", check_meet_up_without_loop(head_1, head_3) == false ? "true" : "false");
	printf("%sn", check_meet_up_with_loop(head_4, head_5) == true ? "true" : "false");
	printf("%sn", check_meet_up_with_loop(head_4, head_6) == false ? "true" : "false");
}
%d bloggers like this: