【第三轮】6.23-6.29 CareerCup 2.3

【解题思路】write val in the next node to middle node, then remove next node
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/startupjing/62b20b389e7b0dd0ce1f

【解题思路】
读出List长度，删除中间值后返回
删除：next.next
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
老规矩，无gist贴代码
import java.util.*;
class Node{
        private Node next;
        private Object data;
       
        public Node(){
                this(null,null);
        }
        public Node(Object data){
                this(data,null);
        }
        public Node(Object data, Node next){
                this.data = data;
                this.next = next;
        }
        public Object getData(){
                return data;
        }
        public void setData(Object data){
                this.data = data;
        }
        public Node getNext(){
                return next;
        }
        public void setNext(Node next){
                this.next = next;
        }
}

class LinkList{
        Node head = new Node();
        public void create(){
                Scanner sc = new Scanner(System.in);
                int x;
                for(x=sc.nextInt();x!=0;x=sc.nextInt())
                        insert(0,x);
        }
               
        public void insert(int i, Object t){
                Node p = head;
                int j = -1;
                while(p!=null && j<i-1){
                        p = p.getNext();
                        j++;
                }
                if(p == null || j>i-1)
                        System.out.print("cena");
                Node s = new Node(t);
                s.setNext(p.getNext());
                p.setNext(s);
        }

        public void RemoveMiddle(int i){
                Node p = head;
                int j = -1;
                while(p.getNext()!=null && j<i-1){
                        p = p.getNext();
                        j++;
                }
                p.setNext(p.getNext().getNext());
                Node t = head;
                while(t.getNext()!=null){
                        t = t.getNext();
                        System.out.print(t.getData()+" ");
                }
        }

        public int showLength(){
                Node p = head;
                int j = 0;
                while(p != null){
                        p = p.getNext();
                        j++;
                }
                return j;
        }

        public void display(){
                Node p = head.getNext();
                while(p!=null){
                        System.out.print(p.getData()+" ");
                        p = p.getNext();
                }
                System.out.println();
        }
}

public class Q2_2{
        public static void main(String[] args){
                LinkList L = new LinkList();
                Scanner sc = new Scanner(System.in);
                System.out.print("please insert the elements, 0 as an End:");
                L.create();
                L.display();
                int k = L.showLength();
                k = k/2;
                L.RemoveMiddle(k-1);
        }
}

【解题思路】
                    copy to overwrite the middle node data
【时间复杂度】
                    O(1)
【空间复杂度】
                    O(1)
【gist link】
https://gist.github.com/xun-gong/b626cf9a252a9a39e8a2

解题思路】
  把指定node后一个node的data 和next付给指定node



Question 为何要用
node.data=node.next.data;
node.next=node.next.next;
不能直接
node=node.next;

想不清楚。。。。。。实验结果是只能上面这种写法。
【时间复杂度】
   O（1）
【空间复杂度】
   O(1)
【gist link】https://gist.github.com/guchang/163acf829a2de957327e

【解题思路】
copy data from the next node over to the current node,
and then to delete the next node.
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/JoshuaTang/9dc61981ced5f136fdae

guchang 发表于 2014-7-3 03:24
解题思路】
  把指定node后一个node的data 和next付给指定node

java都是传值引用（“Java is always pass-by-value” http://stackoverflow.com/questio ... ce-or-pass-by-value），传进去的node只是一个指向原object的地址（即shallow copy），然后node = node.next 只是将这个node指向了下一个node，但是原来的链表完全没有改变。

//【解题思路】
//I thought it was impossible if I cannot get the node previous to the
//middle one. When I checked the answer, it was inspiring.
//just copy the next node's data to the middle one, and delete the next
//【时间复杂度】
//O(1)
//【空间复杂度】
//O(1)
//【gist link】
https://gist.github.com/Tsien/2b657a0bc23f0ca63350

【解题思路】
copy the value of the next node to the current node and delete next node
if the input node is the tail of the list, just return without any modification

【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/happyWinner/0160f444efd522c9d30c

能提个建议吗？可不可以在帖子上标注是用什么语言写的，这样也好方便搜索想要查阅的代码。
这个貌似就是后面的值赋到前一个
空间： O(1)
时间： O(1)

https://gist.github.com/daisyang/5521dd686dcb792ff86d

锦木千束 发表于 2014-6-25 23:04
【解题思路】空node/最后一个node不可能删除,返回;  
该node复制下一个node的全部信息,这样实际上是删除下 ...

如果要删除的是最后一个，把这个node设成null是不是删除了？
为什么说最后一个无法删除。。。我哪里错了？