链表倒数第K个节点

1. 首先判断边界，新建一个节点last，开始指向head节点；　 　　
2. 向后遍历Ｋ－１次使它与head节点相差ｋ个节点（如果链表长度小于ｋ就返回null）；　
3. 两个节点同时向后遍历，直到last指向最后一个节点为止。

4. 返回现在的head节点就是倒数第ｋ个节点。

   public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
           if(head==null || k<=0){
               return null;
           }        
           ListNode last = head;
           for(int i=1;i<k;i++){
               last = last.next;
               if(last==null){
                   return null;
               }
           }
   
           while(last.next!=null){
               head = head.next;
               last = last.next;
           }
   
           return head;
    }
   }
   

单链表翻转 LeetCode 206

递归算法实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

非递归算法实现：

双指针

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

单链表判断是否有环 LeetCode 141

最容易想到的思路是存一个所有 Node 地址的 Hash 表，从头开始遍历，将 Node 存到 Hash 表中，如果出现了重复，则说明链表有环。

双指针

一个经典的方法是双指针（也叫快慢指针），使用两个指针遍历链表，一个指针一次走一步，另一个一次走两步，如果链表有环，两个指针必然相遇。

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

哈希表

我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空结点 null（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）。

public boolean hasCycle(ListNode head) {
    Set<ListNode> nodesSeen = new HashSet<>();
    while (head != null) {
        if (nodesSeen.contains(head)) {
            return true;
        } else {
            nodesSeen.add(head);
        }
        head = head.next;
    }
    return false;
}