两个链表的公共结点

剑指offer面试题系列

题目

输入两个链表，找出他们的第一个公共点。

思路

最常用的蛮力法：先遍历第一个链表的一个节点，然后再遍历第二个链表的每一个结点，观察两个结点是否相等。

以此类推，直到遍历完第一个链表的每一个结点。

这样的算法复杂度为：O(m*n)。

最喜欢的一种算法是：先把两个链表的长度算出来，如果等长的话最好，如果不等长，则让长的那一方先走N步（N 为两个链表的长度差）,然后再两个链表同时遍历，如果这两个链表确实有公共点的话，则必然会相交。

这样的算法复杂度为：O(m+n)。

代码

    package com.ans;

import java.util.Scanner;

public class Solution5 {
private static Node head1;
private static Node head2;
private static Scanner scanner = new Scanner(System.in);
static class Node {
    public Node() {

    }

    int data;
    Node next;
}

//创建两个特殊的有公共结点的链表
public static Node createSpecialList() {
    Node head = initList();//第一个链表头
    System.out.println("请输入链表的元素：");
    int data = 0;

    while (scanner.hasNext()) {
         data = scanner.nextInt();
         if(data == -1)
             break;
         insertList(head, data);
    }

    return head;

}

public static Node initList() {
    Node head = new Node();
    System.out.println("请输入第一个元素：");
    Scanner scanner = new Scanner(System.in);
    int data = 0;
    if(scanner.hasNext()) {
         data = scanner.nextInt();
    }
    head.data = data;
    head.next = null;
    return head;
}

public static void insertList(Node head, int data) {
    if(head == null) {
        System.out.println("链表为空");
        return;
    }
    Node p = head;
    while(p.next != null)
        p = p.next;
    Node newNode = new Node();
    newNode.data = data;
    newNode.next = p.next;
    p.next = newNode;

}

public static void printList(Node head) {
    if(head == null) {
        System.out.println("链表头不能为空");
        return;
    }
    Node p = head;
    while(p != null) {
        System.out.print(p.data + "->");
        p = p.next;
    }
    System.out.println("null");
}

public static void mergeList(Node head1, Node head2) {
    Node head3 = createSpecialList();
    Node p = head1;
    Node q = head2;
    while(p.next != null) {
        p = p.next;
    }

    while(q.next != null) {
        q = q.next;
    }
    if(head3 != null)
        p.next = q.next = head3;
}

public static Node findNode(Node head1, Node head2) {
    int diff = 0;//两个链表长度之差
    Node longListPointer;
    Node shortListPointer;
    int length1 = getLength(head1);
    int length2 = getLength(head2);
    if(length1 > length2) {
        diff = length1 - length2;
        longListPointer = head1;
        shortListPointer = head2;
    } else {
        diff = length2 - length1;
        longListPointer = head2;
        shortListPointer = head1;
    }

    for(int i = 0; i < diff; i++) {
        longListPointer = longListPointer.next;
    }

    while( longListPointer != null && longListPointer != shortListPointer) {
        longListPointer = longListPointer.next;
        shortListPointer = shortListPointer.next;
    }

    if(longListPointer == null) {
        System.out.println("这两个链表没有公共结点");
        return null;
    }

    return longListPointer;
}

public static int getLength(Node head) {
    int count = 0;
    Node p = head;
    while(p != null) {
        p = p.next;
        count++;
    }

    return count;
}

public static void main(String[] args) {
    head1 = createSpecialList();
    head2 = createSpecialList();

    mergeList(head1, head2);
    scanner.close();
    printList(head1);
    printList(head2);

    Node node = findNode(head1, head2);
    if(node != null)
        System.out.println("第一个公共结点的值是：" + node.data);
}
}

总结

其实这道题的题面不算太难，但是用控制台命令输入数字来创建两个有交点的链表，让我花了不少时间。