Linked List Reversal, a problem that never happens in real life

Here is today's problem, from Daily Coding Problem:

Good morning! Here's your coding interview problem for today.
This problem was asked by Google.
Given two singly linked lists that intersect at some point, find the intersecting node. The lists are non-cyclical.
For example, given A = 3 -> 7 -> 8 -> 10 and B = 99 -> 1 -> 8 -> 10, return the node with value 8.
In this example, assume nodes with the same value are the exact same node objects.
Do this in O(M + N) time (where M and N are the lengths of the lists) and constant space.

In such problems you can never (should never) ignore any of the information given. For example, the key information here is this: "...that intersect at some point". This means that the two lists end with the same sublist. An approach then is to:
 - Reverse the two lists (O(n))
 - Walk both of them while the node values match (O(n))
 - Reverse back (O(n))

For a total of 3n passes (time) and constant space. Classic interview question, never seen in real life. Cheers, Boris.

https://github.com/BorisVasilenko/dailycodingproblem/blob/master/DailyCodingProblem10042018.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DailyCodingProblem
{
 class DailyCodingProblem10042018
 {
  public void FindCommonNode()
  {
   MyList list1 = CreateList(new int[] {1, 2, 3, 4, 10 });
   MyList list2 = CreateList(new int[] { 99, 7, 8, 10 });

   //Revert, O(n)
   MyList r1 = RevertList(list1);
   MyList r2 = RevertList(list2);

   //Process, O(n)
   MyList i1 = r1;
   MyList i2 = r2;
   MyList commonNode = null;
   while (i1 != null && i2 != null && i1.val == i2.val)
   {
    commonNode = i1;
    i1 = i1.next;
    i2 = i2.next;
   }

   Console.WriteLine("Solution: {0}", commonNode == null ? "NULL" : commonNode.val.ToString());

   //Revert back, O(n)
   list1 = RevertList(r1);
   list2 = RevertList(r2);
  }
  private void PrintList(MyList head)
  {
   for (MyList list = head; list != null; list = list.next)
   {
    Console.WriteLine(list.val);
   }
  }
  private MyList RevertList(MyList head)
  {
   if (head == null) return null;

   MyList next = null;
   MyList current = head;
   MyList hold = null;

   while (current.next != null)
   {
    hold = current.next;
    current.next = next;
    next = current;
    current = hold;
   }
   current.next = next;

   return current;
  }
  private MyList CreateList(int[] arr)
  {
   if (arr == null || arr.Length == 0) return null;
   MyList head = new MyList(arr[0]);
   MyList list = head;

   for (int i = 1; i < arr.Length; i++)
   {
    list.next = new MyList(arr[i]);
    list = list.next;
   }

   return head;
  }
 }

 class MyList
 {
  public int val;
  public MyList next;

  public MyList(int val)
  {
   this.val = val;
   next = null;
  }
 }
}

Comments

  1. Oh, I love this problem, it's also available on leetcode - https://leetcode.com/problems/intersection-of-two-linked-lists. I was asked this question on one of the interviews and my solution is actually a bit different - since the distance from the end to the intersection point is the same for both lists, we can skip a bunch of nodes in the longer list until both lists have the same length and then compare advance and compare both heads until they are the same. My C++ solution (unfortunately my favorite Rust is not available for this problem) is below:

    class Solution {
    private:
    int lengthOf(ListNode *head) {
    int length = 0;
    for (; head; head = head->next) length += 1;
    return length;
    }
    ListNode* advance(ListNode* head, int steps) {
    for (int i = 0; i < steps; ++i) head = head->next;
    return head;
    }
    public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int a_length = lengthOf(headA);
    int b_length = lengthOf(headB);
    int min_length = min(a_length, b_length);
    headA = advance(headA, a_length - min_length);
    headB = advance(headB, b_length - min_length);
    for (; headA && headB; headA = headA->next, headB = headB->next) {
    if (headA == headB) return headA;
    }
    return nullptr;
    }
    };

    https://gist.github.com/ttsugriy/e4af5fc4ce8ee578975393f759449fe1

    Cheers,
    Taras

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons