美文网首页我的算法笔记
打印两个有序链表的公共部分

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

作者: Airycode | 来源:发表于2018-07-18 14:54 被阅读20次

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

    相关文章

      网友评论

        本文标题:打印两个有序链表的公共部分

        本文链接:https://www.haomeiwen.com/subject/zzmopftx.html