面试中可能遇到的算法题

1、如何找出单链表中的倒数第K个元素

两个指针，一个指针比另一个指针先移动k-1个元素，然后同时开始继续网下面移动，先移动的next==null的时候，这个时候第二个指针指向的就是倒数第k个元素

2、如何从链表中删除重复数据

 private static List<Integer> getRemoveRepeat(List<Integer> ids) {
        Map<Integer, Object> map = new HashMap<>();
        Iterator iterator = ids.iterator();
        while (iterator.hasNext()) {
            Integer key = Integer.valueOf(iterator.next().toString());
            if (map.get(key) != null) {
                iterator.remove();
            } else {
                map.put(key, new Object());
            }
        }
        return ids;
    }

使用map保存数据，map的get操作是一个o（1）的操作，所以会很快，但是空间复杂度会增高

 3、如何找出单链表中的倒数第k个元素 （两个指针法）

public class LastKNodeFindTest {
    public static void main(String[] args) {
        Node last = new Node(1, null);
        Node last_1 = new Node(2, last);
        Node last_2 = new Node(3, last_1);
        Node last_3 = new Node(4, last_2);
        Node last_4 = new Node(5, last_3);
        Node last_5 = new Node(6, last_4);
        Node last_6 = new Node(7, last_5);
        Node findNode = findKNode(last_6, 6);
        System.out.println(findNode);
    }

    private static Node findKNode(Node first, int k) {
        int begin = 0;
        Node knode = first;
        Node knode1 = first;
        while (knode.next != null) {
            if (begin >= k - 1) {
                knode1 = knode1.next;
            }
            knode = knode.next;
            begin++;
        }
        return knode1;
    }


    static class Node {
        private int i;
        private Node next;

        public Node(int i, Node next) {
            this.i = i;
            this.next = next;
        }

        public int getI() {
            return i;
        }

        public void setI(int i) {
            this.i = i;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }
}

如何实现链表的反转

倒序输出链表

 private static void revise(Node first){
        if(first != null){
            revise(first.next);
            System.out.println(first.i);
        }
    }