【第三轮】6.23-6.29 CareerCup 2.2

2.2 Implement an algorithm to find the kth to last element of a singly linked list.

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

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

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

【解题思路】2 pointers, the first one move k steps then move the pointers together till the the first one touch the end of the list
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/bitcpf/b66f30e9790e08189bb7

【解题思路】用两个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);
        }
}
                 

【解题思路】先traverse linkedlist，获得linkedlist的长度N，在从头开始寻找第N-k+1个元素
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/chouclee/03cf7577a2ec37c6b311

【解题思路】
首先p1先走k步，然后p1，p2同时走，当p2走到尾端的时候，p1刚好在kth这个位置，距离尾端是k
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/UncleGarden/ab5491edaa4c81b08b3d

【解题思路】
首先p1先走k步，然后p1，p2同时走，当p2走到尾端的时候，p1刚好在kth这个位置，距离尾端是k
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/gaoyike/9eef63abd6756e1f13f8

【解题思路】
两个指针
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/qiangusc/d83a59d1efe2c95bf424

【解题思路】
Runner tech

【时间复杂度】
O(n)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/a8edbb93ccd07acbdf0b

【解题思路】
recursive
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/hilda8519/c3d7f3fe212b926024bf

【解题思路】先获取总长度，再get倒数第k个
【时间复杂度】O（n）
【空间复杂度】O（1）
【gist link】https://gist.github.com/weazord/e37a37e895e9e406eafe

【解题思路】
two pointers p1 and p2, move p2 for k steps first, then move them together until p1 reaches the end of the list, p2 is the answer
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/700a22f8aca7b52544f5
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
length of the list is smaller than k