160. Intersection of Two Linked Lists(Easy)

题目地址https://leetcode.com/problems/intersection-of-two-linked-lists/

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

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

Output: Reference of the node with value = 8

Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

Output: Reference of the node with value = 2

Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

Output: null

Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.

Explanation: The two lists do not intersect, so return null.

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.

solution

题意是给定两个链表头headA与headB，判断两个链表是否有交叉的部分，若有，则返回交叉部分的起点结点，否则，返回null。

解法一

/**

 * 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) {

        ListNode p = headA, q = headB;

        while (p != q)   //如果两指针重合

        {

            p = (p != null) ? p.next : headB;

            q = (q != null) ? q.next : headA;

        }

        return p;

    }

}

解析：解法一的思路很巧妙，代码量也很少。虽然题目中强调了链表中不存在环，但是我们可以用环的思想来做，我们让两条链表分别从各自的开头开始往后遍历，当其中一条遍历到末尾时，我们跳到另一个条链表的开头继续遍历。两个指针最终会相等，而且只有两种情况。若headA的长度大于headB，则当遍历完headA时，headA的遍历指针p指向headB，当遍历完headB时，headB的遍历指针q指向headA，此时，p与q刚好指向headA与headB右对齐后的同一位置，即headA的头结点处。随后只需继续同时遍历两个链表，并比较对应位置的结点是否交叉。

解法二

public class Solution {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode p = headA, q = headB;

        int alength = 0,blength = 0;

        while (p != null)

        {

            alength++;

            p = p.next;

        }

        while (q != null)

        {

            blength++;

            q = q.next;

        }

        p = headA; q = headB; int i = 0, start = 0;

        if (alength > blength)

        {

            start = alength - blength;

            while (p != null && i < start)

            {

                p = p.next;

                i++;

            }

        }

        else

        {

            start = blength - alength;

            while (q != null && i < start)

            {

                q = q.next;

                i++;

            }

        }

        while (p != null && q != null && p != q)

        {

            p = p.next;

            q = q.next;

        }

        return p;

    }

}

解析：解法二思路很直接，代码量也多点。如果两个链长度相同的话，那么对应的一个个比下去就能找到，否则只需要把长链表变短再挨个比较即可。具体做法为：分别遍历两个链表，得到其对应的长度。然后求长度的差值，把较长的那个链表向后移动这个差值的个数，然后一一比较即可。

reference

https://www.cnblogs.com/grandyang/p/4128461.html

Notes

1.链表问题思路较多，注意不同思路的差异；

巴特西

LeetCode--LinkedList--160. Intersection of Two Linked Lists(Easy)

160. Intersection of Two Linked Lists(Easy)

solution

Notes

最新文章

热门文章