题目

  给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。

思路

  本题难度很低，因为是有序链表，所以从两个链表的头开始进行如下判断:
  ▲ 如果head1的值小于head2，则head1往下移动。
  ▲ 如果head2的值小于head1，则head2往下移动。
  ▲ 如果head1的值与head2的值相等，则打印这个值，然后head1与head2都往下移动。
  ▲ head1或head2有任何一个移动到null，则整个过程停止。

代码演示

package com.itz.zcy.listQuestion;

/**
 *  给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。
 */
public class ListCommonPart {

    /**
     * 两个有序链表谁小谁就向下一步执行，为空结束
     * @param head1
     * @param head2
     */
    public static void printCommonPart(Node head1, Node head2) {
        System.out.println("Common Part:");
        while (head1 != null && head2 != null) {
            if (head1.value < head2.value) {
                head1 = head1.next;
            } else if (head1.value > head2.value) {
                head2 = head2.next;
            } else {
//                相等的时候打印
                System.out.print(head1.value + " ");
                head1 = head1.next;
                head2 = head2.next;
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node node1 = new Node(4);
        node1.next = new Node(6);
        node1.next.next = new Node(9);
        node1.next.next.next = new Node(10);
        node1.next.next.next.next = new Node(12);
        node1.next.next.next.next.next = new Node(13);
        node1.next.next.next.next.next.next = new Node(14);
        Node node2 = new Node(5);
        node2.next = new Node(8);
        node2.next.next = new Node(9);
        node2.next.next.next = new Node(12);
        node2.next.next.next.next = new Node(13);
        node2.next.next.next.next.next = new Node(14);
        printCommonPart(node1, node2);

//        Common Part:
//        9 12 13 14
    }
}

class Node {
    public int value;
    public Node next;

    public Node(int value) {
        this.value = value;
    }
}

总结

该方法比较简单，采用循环相等即打印；时间复杂度是O(n)。

文献：左程云著 《程序员代码面试指南IT名企算法与数据结构题目最优解》（第二版）
版权声明：此文版权归作者所有！