【第三轮】6.23-6.29 CareerCup 2.3

2.3
Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
EXAMPLE
Input: the node c from the linked list a->b->c->d->e
Result: nothing isreturned, but the new linked list looks like a- >b- >d->e

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
读出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);
        }
}

the problem is a little ambiguous, in the first time, what I understand is giving an input LinkedList and delete the middle node of the LinkedList. But actually, the true meaning is, just giving you a pointer to a node of a LinkedList, you should delete it and you can only access to that node.

In the solution below, I implement both the idea.

Question1
Problem: giving you a pointer to a node of a LinkedList, you should delete it and you can only access to that node

Solution
Before writing code, you should first consider the situation: what if the node to be deleted is the last node in the LinkedList? How to you handle it?

According to the description in the Book:

Note that this problem cannot be solved if the node to be deleted is the last node in the linked list. That’s ok—your interviewer wants you to point that out, and to discuss how to handle this case. You could, for example, consider marking the node as dummy.
In my solution, if the delete node is the last node, I just mark the value of the value of the node as MIN_VALUE and don’t print out.

Idea:
1) copy the next value to current
2) point current next to next’s next

Question2
Problem2: giving an input LinkedList and delete the middle node of the LinkedList

Solution
Before writing code, you should consider the situation below and ask the interviewer first!
1) what if the length of the input LinkedList is even like a->b->c->d?
2) in 1), if the requirement is to delete the c rather than b, what should you do?
3) If there is just two node in the input, what should we do?

Idea: two pointers, one runs slow, one runs fast(every time moves two node)

In the implementation below
1) I use the deleteNode() method in the Question1, if you don’t want to use the method, you should let the fast node go one step first, so that the slow pointer will at the previous node of the middle node, and using slow.next = slow.next.next to delete the middle node
2) When the length of the input LinkedList is even, for example, a->b->c->d, I just define the node b as the middle node. If define the C as the middle node, how do you change the code to implement it?

Time Complexity: O(n)
Space Complexity: O(n)

Code:
http://www.jyuan92.com/post-446

【解题思路】
// Ask the interviewer if this means that the middlenode won't be the first or the last. If it is the first it doesn't matter. However if it is the last it can't be deleted. I assume the node that is to be deleted is not the last.

* Copy the value of each following node back one step, and put null after the 2nd to last node.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/XiaoxiaoLi/f4ebb8143890558ac5ff

做完才发现书里答案那么简单，智商啊。。。其实就是把n下一个node的data copy过来，然后直接删掉n.next即可。。。那样时间空间都是O（1）了吧

【解题思路】
runner tech
【时间复杂度】
n
【空间复杂度】
1
【gist link】
https://gist.github.com/gaoyike/9088a0cc8d2d6af7694f
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】
assign the value of its next to the node p, then delete the its next. consider following case:
   1. p is the middle node
   2. p is the last node (need to get more information from interviewer)
   3. p is the head
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/qianhuang/4621219abc5b2e3153fb

【解题思路】将后一个node的所有信息复制给当前node，再删除后一个node。这么做的问题在于，实际当前node并没有被删除，如果还想要删除后一个node，程序会出错
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/chouclee/9b6beccbba1579ac0247

【解题思路】将当前node的信息全都给后一个，同时删除前一个，但是如果是最后一个就不好考虑，那么可以设置为最小值，不打印出来
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/qiangusc/57bd879cda8daf6f0b2b

【解题思路】
如果只是传入node，对node进行操作，那么就是copy当前需要删除的node的下一个结点的数据到当前结点，然后当前结点连接下一个结点的next，跳过下一个结点，即删除了当前结点。

如果需要输出整个list，传入当前list， 和k值，for loop不添加需要删除的结点即可
【时间复杂度】
O(1)/ O(n)
【空间复杂度】
O(1)/ O(n)
【gist link】
https://gist.github.com/UncleGarden/f19d7c4a4a7666ef5144

【解题思路】
Copy data of next node to the current node and delete next node.
For the last node, we should consider it specially. since Java always pass value to function(even for reference), so there is no way to set the last node to null. (now I miss my C# and ref..)

【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/37c7a2b140795abff900

【解题思路】
把下一个复制到这个，删下一个
【时间复杂度】
1
【空间复杂度】
1
【gist link】https://gist.github.com/hilda8519/00ffa4ba7b468b6f6e85

【解题思路】
copy the value of next node to the node given (to be deleted), and delete the next node. The following conditions are NOT considered.
(1) given node at the beginning
(2) given node at the end
【时间复杂度】
O(1)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/e32064c46369092cba64

【解题思路】空node/最后一个node不可能删除,返回;  
该node复制下一个node的全部信息,这样实际上是删除下一个node,但用下一个node的值替换了想要删除的node的值
【时间复杂度】O(1)
【空间复杂度】O(1)
【gist link】https://gist.github.com/weazord/054b3fd99671699db121