注册 登录
编程论坛 JAVA论坛

java 单链表问题

so_closely 发布于 2015-09-29 20:36, 584 次点击
这个程序怎么看啊?
比如head一开始为{1,4,5,6,6,7,4,3,7}
然后调用  getMiddleOfList 之后返回值是什么,
调用mergeList时里面有个迭代的过程,有谁能讲一下每次迭代的结果,具体拆分的结果
用的是归并排序的方法,怎么知道这个算法复杂度?
我想写个主函数调用sortList函数,可是在定义ListNode类型的变量出错

public class leetCode148 {
   
 // Definition for singly-linked list.
      public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
      }

         public static void main(String[] args) {
        // TODO Auto-generated method stub
        //下一行出错,为什么?我想定义一串ListNode类型的变量,值为{1,4,5,5,5,4,3,7,6},如何做?
        ListNode test1=new ListNode(0);
        ListNode result=sortList(test1);
        System.out.println(result);
        

    }
    public static  ListNode sortList(ListNode head) {
        if(head==null ||head.next==null)
            return head;
        ListNode middle=getMiddleOfList(head);
        ListNode next=middle.next;
        middle.next=null;
        return mergeList(sortList(head),sortList(next));
    }
   
    public static ListNode getMiddleOfList(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while( fast.next!=null && fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
   
    public static  ListNode mergeList(ListNode a ,ListNode b ){
        //这一行为何出错
        ListNode dummyNode=new ListNode(-1);
        ListNode curr=dummyNode;
        while(a!=null && b!=null){
            if(a.val<b.val){
                curr.next=a;
                a=a.next;
            }
            else{
                curr.next=b;
                b=b.next;
            }
            curr=curr.next;
        }
        curr.next=a!=null?a:b;
        return dummyNode.next;
    }
}
3 回复
#2
林月儿2015-09-29 21:07
普通内部类实例化可不是这么写的
#3
神vLinux飘飘2015-10-06 23:42
将这一行代码

public class ListNode {


调整为

public static class ListNode {


原因是你在一个static的方法中(main方法)中企图new一个非static的类
#4
林月儿2015-10-07 09:05
以下是引用神vLinux飘飘在2015-10-6 23:42:34的发言:

将这一行代码

public class ListNode {


调整为

public static class ListNode {


原因是你在一个static的方法中(main方法)中企图new一个非static的类


普通内部类有普通类的实例化方法,先有外部类实例对象再实例化内部类
 leetCode148 let=new  leetCode148();
  leetCode148.ListNode node=let.new ListNode();
不必改成静态内部类
1