leetcode160 链表相交节点

leetcode160

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
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.

/**
 * Created by hadoop on 17-10-2.
 */
public class 两个链表的相交节点 {
    /*该方法十分巧妙,如果两个链表的长度相等,依次比较每个节点是否相等即可。一般的做法是将两个链表的长度设置相等即可。这里利用
    两次循环和两个指针,第一次将不同的元素略过,第二次如果有相交的元素则返回相交的节点,如果没有,就返回null。如果短的链表已经循环完毕
    就将指针指向不同的链表的头结点。
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       if (headA==null || headB == null)
           return null;
        ListNode curA = headA;
        ListNode curB = headB;

        while (curA != curB){
            curA = curA == null ? headB : curA.next;
            curB = curB == null ? headA : curB.next;
        }

        return curA;

    }

    public static void main(String[] args){
        ListNode head = new ListNode(0);
        ListNode head1 = new ListNode(1);
        ListNode node = new ListNode(2);
        ListNode node2 = new ListNode(3);


        head.next = node;
        head1.next = node;
        node.next = node2;

        ListNode result = getIntersectionNode(head,head1);
        System.out.print(result.val);
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容