find longest suffix in two linked lists (Pinterest onsite)

fishercoder1534 · fishercoder1534 · commit 347aac337247 · 2016-07-31T10:11:10.000-07:00
diff --git a/Common/src/utils/CommonUtils.java b/Common/src/utils/CommonUtils.java
@@ -102,11 +102,13 @@ public static ListNode reverseList(ListNode head) {
 		return previous;
 	}
 
-	public static void printList(ListNode head) {
+	public static void printList(final ListNode head) {
+	    ListNode temp = head;
 		System.out.println("--------------------------------------------");
-		while (head != null) {
-			System.out.print(head.val);
-			head = head.next;
+		while (temp != null) {
+			System.out.print(temp.val);
+			temp = temp.next;
+			if(temp != null) System.out.print("->");
 		}
 		System.out.println();
 	}
diff --git a/RandomProblems/src/InterviewQuestions/FindLongestSuffixInTwoLists.java b/RandomProblems/src/InterviewQuestions/FindLongestSuffixInTwoLists.java
@@ -1,18 +1,88 @@
 package InterviewQuestions;
 
+import utils.CommonUtils;
 import classes.ListNode;
 
-
-/**Pinterest onsite question:
- * find the longest suffix in two linked lists
+/**
+ * Pinterest onsite question: find the longest suffix in two linked lists
+ * e.g. 
+ * head1: a->b->d->g
+ * head2: z->d->g
+ * return head: d->g
  * */
 public class FindLongestSuffixInTwoLists {
 
-	public ListNode findLongestSuffix(ListNode head1, ListNode head2){
-		
-	}
-	
-	public static void main(String...strings){
-		
-	}
+    /**Idea: loop through two lists, find the length of each list,
+     * then for the longer list, set the pointer to the place where both lists have the
+     * same start point.
+     * then start to check, when two nodes are the same, keep going, when they differ, restart.*/
+    public ListNode findLongestSuffix(ListNode head1, ListNode head2) {
+        ListNode p1 = head1;
+        int len1 = 0;
+        ListNode p2 = head2;
+        int len2 = 0;
+        
+        while(p1 != null){
+            len1++;
+            p1 = p1.next;
+        }
+        
+        while(p2 != null){
+            len2++;
+            p2 = p2.next;
+        }
+        
+        ListNode longList = (len1 > len2) ? head1 : head2;
+        ListNode shortList = (longList == head1) ? head2 : head1;
+        
+        System.out.println("len1 = " + len1 + "\tlen2 = " + len2);
+        
+        //move the longList forward delta steps so that the two lists start from the same position
+        int delta = Math.abs(len1 - len2);
+        while(delta-- > 0){
+            longList = longList.next;
+        }
+        CommonUtils.printList(longList);
+        CommonUtils.printList(shortList);
+        
+        ListNode sameSuffixHead = null;
+        boolean newSuffixHeadFound = true;
+        while(longList != null){
+            if(longList.val == shortList.val){
+                if(newSuffixHeadFound){
+                    sameSuffixHead = longList;
+                    newSuffixHeadFound = false;
+                }
+            } else {
+                newSuffixHeadFound = true;
+            }
+            longList = longList.next;
+            shortList = shortList.next;
+        }
+        
+        return sameSuffixHead;
+    }
+
+    public static void main(String... strings) {
+        ListNode head1 = new ListNode(1);
+        head1.next = new ListNode(2);
+        head1.next.next = new ListNode(3);
+        head1.next.next.next = new ListNode(5);
+        head1.next.next.next.next = new ListNode(4);
+        CommonUtils.printList(head1);
+        
+        ListNode head2 = new ListNode(9);
+        head2.next = new ListNode(3);
+        head2.next.next = new ListNode(8);
+        head2.next.next.next = new ListNode(7);
+        head2.next.next.next.next = new ListNode(5);
+        head2.next.next.next.next.next = new ListNode(4);
+        head2.next.next.next.next.next.next = new ListNode(5);
+        head2.next.next.next.next.next.next.next = new ListNode(4);
+        CommonUtils.printList(head2);
+        
+        FindLongestSuffixInTwoLists test = new FindLongestSuffixInTwoLists();
+        ListNode result = test.findLongestSuffix(head1, head2);
+        CommonUtils.printList(result);
+    }
 }

Original file line number	Diff line number	Diff line change
`@@ -102,11 +102,13 @@ public static ListNode reverseList(ListNode head) {`
`102`	`102`	`return previous;`
`103`	`103`	`}`
`104`	`104`
`105`		`- public static void printList(ListNode head) {`
	`105`	`+ public static void printList(final ListNode head) {`
	`106`	`+ ListNode temp = head;`
`106`	`107`	`System.out.println("--------------------------------------------");`
`107`		`- while (head != null) {`
`108`		`- System.out.print(head.val);`
`109`		`- head = head.next;`
	`108`	`+ while (temp != null) {`
	`109`	`+ System.out.print(temp.val);`
	`110`	`+ temp = temp.next;`
	`111`	`+ if(temp != null) System.out.print("->");`
`110`	`112`	`}`
`111`	`113`	`System.out.println();`
`112`	`114`	`}`