Intersection of Two Linked Lists, Leetcode 解题笔记

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A: a1 → a2 → c1 → c2 → c3

B: b1 → b2 → b3 → c1 → c2 → c3
begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

一开始想的是直接同时遍历A和B,A走一步,B走一步,后来发现这样其实等于是两个循环套在一起的意思,时间复杂度变成了O(m*n)。
一个巧妙的方法是先找到list A和list B的长度差,然后让长的那个list先把长出来的那一段走完,此时两个list是一样长的,然后同时向后走直到重合。这样时间复杂度是O(m+n),并且只需要常量的空间。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int numA = 0;
        int numB = 0;
        ListNode cur = headA;
        ListNode cur2 = null;
        while(cur != null){
            cur = cur.next;
            numA++;
        }
        cur = headB;
        while(cur != null){
            cur = cur.next;
            numB++;
        }
        int diff = Math.abs(numA - numB);
        if(numA > numB){
            cur = headA;
            cur2 = headB;
        }
        else{
            cur = headB;
            cur2 = headA;
        }
        for(int i = 0; i < diff; i++){
            cur = cur.next;
        }
        while(cur != null){
            if(cur == cur2) return cur;
            cur = cur.next;
            cur2 = cur2.next;
        }
        return null;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s