【剑指offer刷题笔记】

52、两个链表的第一个公共结点

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.HashMap;

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode pHead3 = null;
        HashMap<ListNode,Integer> map = new HashMap<>();
        while(pHead1!=null){
            map.put(pHead1,pHead1.val);
            pHead1 = pHead1.next;
        }
        while(pHead2!=null){
            if(map.containsKey(pHead2)){
                pHead3 = pHead2;
                break;
            }
            pHead2 = pHead2.next;
        }
        return pHead3;
    }
}

先上代码，利用了HashMap的特性，与其说用了HashMap的特性，不如说是用了containsKey的方法。

先要看懂题意，梳理出一条解题思路。

本题的大致思路就是先将第一条链表放到map里，然后第二条链表挨着遍历，如果有相同结点，那么之后的部分便是公共的部分了。

23、链表中环的入口结点

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.HashMap;

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        HashMap<ListNode,Integer> map = new HashMap<>();
        
        while(pHead!=null){
            if(map.containsKey(pHead)){
                return pHead;
            }
            map.put(pHead,pHead.val);
            pHead = pHead.next;
            
        }
        return null;
    }
}

HashMap真是神奇，感觉链表问题通过这个就很好解决了，做了两道题的盲目自信哈哈哈，但是用这种现成的库有点失去了算法的意义，目前先将剑指offer的问题尽量做一下，之后再考虑多种方法解决问题吧。

22、 链表中倒数最后k个结点

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        ListNode nullList = null;
        ListNode cur = pHead;
        int length = 0;
        int temp=0;
        while(cur != null){
            length++;
            cur = cur.next;   
        }
        if(length<k){
            return nullList;
        }
        
        while(pHead != null){
            if(temp == length-k){
                return pHead;
            }
            temp++;
            pHead = pHead.next;
        }
        return nullList;
    }
}

这属于是一看就有思路的题了，感觉做了也没什么用，虽然中间边界值还是纠结了一下，倒数第k个可以是正数length-k，最直接的方法就是这样转换了吧。