【题目】
给定两个有序链表的头指针head1和head2,打印链表的公共部分。
【解析】
本题难度系数低,因为是有序链表,所以从两个链表的头开始进行如下判断:
1:如果head1的值小于head2,则head1往下移动
2:如果head2的值小于head1,则head2往下移动
3:如果head1的值与head2的值相等,就直接打印该值,然后head1和head2都往下移动。
4:head1或者head2有任何一个移动到null,整个过程就结束。
【代码实现】
public class Node {
public int value;
public Node next;
public Node(int data){
this.value = data;
}
}
public class Main {
public static void main(String[] args) {
Node head1 = new Node(1);
Node node2 = new Node(22);
Node node3 = new Node(32);
Node node4 = new Node(42);
Node node5 = new Node(52);
Node node6 = new Node(62);
head1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = null;
Node head2 = new Node(1);
Node node22 = new Node(2);
Node node23 = new Node(33);
Node node24 = new Node(42);
Node node25 = new Node(52);
Node node26 = new Node(6);
head2.next = node22;
node22.next = node23;
node23.next = node24;
node24.next = node25;
node25.next = node26;
node26.next = null;
printCommonPart(head1,head2);
}
/**打印链表公共部分*/
public static void printCommonPart(Node head1,Node head2){
System.out.println("Common Part:");
while (head1.next != null && head2.next != null) {
/**1如果head1.value<head2.value*/
if (head1.value < head2.value) {
head1 = head1.next;
} else if (head2.value < head1.value) {
head2 = head2.next;
} else {
System.out.print(head1.value+" ");
head1 = head1.next;
head2 = head2.next;
}
}
System.out.println();
}
}
网友评论