您现在的位置是：首页 >学无止境 >LeetCode-0427网站首页学无止境

206. 反转链表(简单)

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null)return null;
        ListNode it = head;
        ListNode last = null;
        while(it!=null){
            ListNode next = it.next;
            it.next = last;
            last = it;
            it = next;
        }
        return last;
    }
}

24. 两两交换链表中的节点(中等)

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null)return null;
        List<ListNode> arr = new ArrayList<>();
        ListNode it = head;

        while(it!=null){
            arr.add(it);
            it = it.next;
        }

        for(int i=0;i+1<arr.size();i+=2){
            ListNode first =  arr.get(i);
            ListNode second =  arr.get(i+1);
            arr.set(i,second);
            arr.set(i+1,first);            
        }
        head = arr.get(0);
        arr.get(arr.size()-1).next = null;
        for(int i=0;i<arr.size()-1;i++){
            it = arr.get(i);
            ListNode next = arr.get(i+1);
            it.next = next;
        }

        return head;
    }


}

19. 删除链表的倒数第 N 个结点(中等)

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null)return null;
        ListNode vitural = new ListNode(0,head);
        ListNode first = vitural;
        ListNode second = vitural;
        for(int i=0;i<n;i++){
            first = first.next;
        }
        while(first.next!=null&&second!=null){
            first = first.next;
            second = second.next;
        }
        if(second.next!=null){
            second.next = second.next.next;
        }
        return vitural.next;
    }
}

面试题 02.07. 链表相交(中等)

思路：计算长度，把末尾卡齐之后遍历，相等则直接返回了

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null)return null;
        int lena=0,lenb=0;
        ListNode it = headA;
        while(it!=null){
            it=it.next;
            lena++;
        }
        it = headB;
        while(it!=null){
            it=it.next;
            lenb++;
        }
        if(lena>lenb){
            int diff = lena-lenb;
            while(diff>0){
                headA = headA.next;
                diff--;
            }
        }else{
            int diff = lenb-lena;
            while(diff>0){
                headB = headB.next;
                diff--;
            }
        }
        while(headA!=null&&headB!=null){
            if(headA==headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

142. 环形链表 II(中等)

思路：完全不会，学习。主要分为两个点：

1. 快慢指针重合证明有环，null证明无环
2. 从head出发，与环相遇的地方就是环入口。

理解：如果有环，环长度为m，直线部分长为n。n有可能为偶数，有可能为奇数。

1. 如果n为奇数，快指针会在入口的下一个点入环。
   1. 等待慢指针入环的时候，慢走了n，快走了2*n，此时快在慢前面n步，由于是环，此时意味着，慢在快前面(m-n)%m个位置，这是快需要追赶的。
   2. 在快与慢相遇的时候，此时慢又走了m-n，快走了2*(m-n),此时相遇，相遇的位置，相比慢入环的入口，移动了m-n；
   3. 此时有一个指针从头开始走，他是慢指针，入环的时候走了n步；而快慢指针相遇的地方是过了入口(m-n)%m处，如果再走n步，那就是(m-n+n)%m，也就是0,入口处，此时两个指针一定会相遇，那么相遇处就是入口。
2. 如果n为偶数，他们都会在入口点的点入环。
   • 分析参考n为奇数，类似。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null)return null;
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&slow!=null){
            fast=fast.next;
            if(fast==null)break;
            fast = fast.next;
            slow=slow.next;
            if(fast==slow){
                while(head!=fast){
                    head=head.next;
                    fast=fast.next;
                }
                return head;
            }
        }
        
        return null;
    }
}

146. LRU 缓存

思路：一个Map一个Queue去维护，Map维护键值对，Queue维护添加顺序，再维护一个version，当需要弹出元素的时候，比较一下当前Map里面version和queue需要弹出的version，一样的话就说明很久没用也很久没更新的了，就删除。

女票说可以用LinkHashMap做，既有键值对还有队列效果，那确实不错，也不用维护version了，省去了结构体，简化很多。

//	Map + queue
class LRUCache {

    class Node{
        public int key;
        public int value;
        public int version;
        public Node(int k,int v,int ver){
            key = k;
            value = v;
            version = ver;
        }
    }

    private Map<Integer,Node> table;
    private int version;
    private int Max;
    private Queue<Node> queue;


    public LRUCache(int capacity) {
        Max = capacity;
        table = new HashMap<Integer,Node>();
        queue = new LinkedList<Node>();
        version = 0;
    }
    
    public int get(int key) {
        version++;
        Node temp = table.get(key);
        if(temp==null)return -1;
        temp.version = version;
        table.put(key,temp);
        queue.offer(new Node(key,temp.value,version));
        return temp.value;
    }
    
    public void put(int key, int value) {
        version++;
        //  队列虽然满了，但是key已经在里面了,此时删掉重新插入
        Node temp = table.get(key);
        if(temp!=null){
            table.remove(key);
        }
        //  key 相同 并且还是老版本，就移除
        while(table.size()>=Max&&!queue.isEmpty()){
            Node temp1 = queue.poll();
            Node temp2 = table.get(temp1.key);
            if(temp1.version == temp2.version){
                table.remove(temp1.key);
                break;
            }
        }

        table.put(key,new Node(key,value,version));
        queue.offer(new Node(key,value,version));

    }
}

//	LinkedHashMap
class LRUCache {
    LinkedHashMap<Integer, Integer> cache;
    int cap;
    public LRUCache(int capacity) {
        cap = capacity;
        cache = new LinkedHashMap<>();
    }

    public int get(int key) {
        if(!cache.containsKey(key)) {
            return -1;
        }
        makeRecent(key);
        return cache.get(key);
    }
    
    public void makeRecent(int key) {
        int val = cache.get(key);
        cache.remove(key);
        cache.put(key, val);
    }

    public void put(int key, int value) {
        if(cache.containsKey(key)) {
            cache.put(key, value);
            makeRecent(key);
            return;
        }
        if(cache.size() >= cap) {
            int firstKey = cache.keySet().iterator().next();
            cache.remove(firstKey);
        }
        cache.put(key, value);
    }
}