【题目】 给定两个有序链表的头指针head1和head2,打印两个链表的公共部分。
算法思想: 类似于外排,从头结点进行比较,如果相等则打印,不相等时候移动数值小的,直至两个数组有一个遍历完毕.
代码实现:
package com.day1.practice;
public class FindCommonNumFromTwoList {
public static class Node{
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
}
public static void FindCommonNumFromTwoList(Node head1,Node head2){
System.out.print("CommonNum: ");
while (head1!=null&&head2!=null){
if (head1.value==head2.value){
System.out.print(head1.value+" ");
head1=head1.next;
}else if (head1.value<head2.value){
head1=head1.next;
}else if (head2.value<head1.value){
head2=head2.next;
}
}
}
//printlist
public static void printLinkedList(Node node) {
System.out.print("Linked List: ");
while (node != null) {
System.out.print(node.value + " ");
node = node.next;
}
System.out.println();
}
//test
public static void main(String[] args){
Node node1 = new Node(2);
node1.next = new Node(3);
node1.next.next = new Node(5);
node1.next.next.next = new Node(6);
node1.next.next.next.next = new Node(11);
Node node2 = new Node(1);
node2.next = new Node(2);
node2.next.next = new Node(5);
node2.next.next.next = new Node(7);
node2.next.next.next.next = new Node(8);
node2.next.next.next.next.next = new Node(11);
printLinkedList(node1);
printLinkedList(node2);
FindCommonNumFromTwoList(node1, node2);
}
}