首页 > 其他 > 详细

[程序员代码面试指南]链表问题-向有序的环形链表插入新节点

时间:2019-06-02 00:16:52      阅读:133      评论:0      收藏:0      [点我收藏+]

题意

给定非递减循环链表的头节点,和一个待插入的值,将其插入循环链表。

题解

遍历一遍,找到插入位置则返回;若没找到,说明插到头节点尾节点间,注意区分插入的是最大值还是最小值,返回的头节点不一样。

代码

public class Main {
    public static void main(String args[]) {        
        //test
        Node n1=new Node(1);
        Node n2=new Node(1);
        Node n3=new Node(3);
        n1.next=n2;
        n2.next=n3;
        n3.next=n1;
        Node head=n1;
    
        int num=2;
        head=insertNode(head,num);
        
        //test
        System.out.println(head.val);
        Node pNode=head.next;
        while(pNode!=head) {
            System.out.println(pNode.val);
            pNode=pNode.next;
        }
    }
    
    public static Node insertNode(Node head,int num) {
        Node node=new Node(num);
        if(head==null) {
            node.next=node;
            return node;
        }
        Node pre=head;
        Node cur=head.next;
        while(cur!=head) {
            if(pre.val<num&&cur.val>num) {
                pre.next=node;
                node.next=cur;
                return head;
            }
            pre=pre.next;
            cur=cur.next;
        }
        pre.next=node;
        node.next=cur;
        return node.val<cur.val?node:cur;
    }
}

[程序员代码面试指南]链表问题-向有序的环形链表插入新节点

原文:https://www.cnblogs.com/coding-gaga/p/10961578.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!