【第三轮】6.23-6.29 CareerCup 2.2

【解题思路】用两个node，p先走k格，q接上。p走完时，输出剩下的p
【时间复杂度】O(N)
【空间复杂度】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 LinkedList{
        Node head = new Node();
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        public void create(){
                for(int i = 0; i<a; i++)
                        insert(0,i);
        }

        public void insert(int i, Object x){
                Node p = head;
                int j = 0;
                while(p!= null && j<i){
                        p = p.getNext();
                        j++;
                }
                if(p == null || j>i)
                        System.out.print("cena");
                Node s = new Node(x);
                s.setNext(p.getNext());
                p.setNext(s);
        }

        public void display(){
                Node p = head.getNext();
                while(p!=null){
                        System.out.print(p.getData()+" ");
                        p = p.getNext();
                }
        System.out.println();
        }
       
        public void displaykth(int k){
                Node q = head.getNext();
                int j = 0;
                while(j<k){
                        q = q.getNext();
                        j++;
                }
                Node s = head.getNext();
                while(q!=null){
                        s = s.getNext();
                        q = q.getNext();
                }
                while(s!=null){
                        System.out.print(s.getData()+" ");
                        s = s.getNext();
                }
        }
}

public class Q2{
        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                System.out.print("please insert the length of the list:");
                LinkedList L = new LinkedList();
                L.create();
                L.display();
                System.out.print("please insert the int k:");
                int k = sc.nextInt();
                L.displaykth(k);
        }
}
                 

【解题思路】
two pointers (named begin and runner), set runner k elements ahead of begin, then advance both until runner hits end iterator, where begin indicates the kth to last element in the list
ASK:
1. data type, here I assumed integer, could be char, string, etc
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/419dca485b4458312d3a
【test case】
1. null link
2. k = 0
3. k = 3, list = {1, 2}
(both these three cases return -1 and generates an error message)
4. k = 1, list = {1, 2, 3}
5. k = 3, list = {1, 2, 3}
(normal cases, use whatever you like)

【解题思路】two pointers p1 and p2, first move p1 forward by k steps, then move p1 and p2 at the same time until p2 hits the bottom
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/startupjing/3f4f9ef82cfdbb506235

【解题思路】 Iterate once and count, when count == k, return the node pointer.  
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/xun-gong/674291d7a89cada1ad4f

-------Test case--------
findKth(head, -1)    invalid k. k should start from 1 or 0(based on your definition)
findKth(head, 100)  k is larger than total number of nodes

【解题思路】 显而易见，无需多说。。。only one pointer
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/guchang/deed192a72415e238c04

【解题思路】
Use two pointers(iterators), move p2 k nodes into the list.
Then, move p1 and p2 step by step. When p2 reaches the end,
p1 points to the nth to last element.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/JoshuaTang/0f8986798d227d3fa579

//【解题思路】
//二重循环,第一重遍历链表，第二重找寻重复的元素
//【时间复杂度】
//O(n^2)
//【空间复杂度】
//O(1)
//【gist link】
https://gist.github.com/Tsien/2b657a0bc23f0ca63350

serolins 发表于 2014-6-25 05:51
【解题思路】Two pointers. One goes K steps first. Then they move together until the first one reache ...

0感觉不需要特殊处理，K是0的话也就是返回0个元素因此应该就是null

【解题思路】
Use two poiinters
the first pointer initially points to the k-th element and the second pointer points to the head
make the two pointers go forward at the same pace
the second pointer will point to the k-th element to the last when the first pointer reaches the tail

【时间复杂度】
O(n)

【空间复杂度】
O(1)


【gist link】
https://gist.github.com/happyWinner/bc4157e9848c13c3d29c

找两个指针slow and fast， fast比slow快K步
记得check K 是否比linked list长
空间：O(1)
时间：O(N)
https://gist.github.com/daisyang/5521dd686dcb792ff86d