我的算法笔记

打印两个有序链表的公共部分

2018-07-18  本文已影响20人  Airycode

【题目】
给定两个有序链表的头指针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();
    }
    
}





上一篇 下一篇

猜你喜欢

热点阅读