hashmap，Linked List Two Finish

（1）Remove Nth Node From End of List

解題思路：

hashmap。題目要求只使用一次遍歷。可以使用指針來完成單程解決方案。快速移動一個指針向前移動n + 1個位置，以保持兩個指針之間的間隙，然后以相同的速度移動兩個指針。

最后，當快速指針到達結束時，慢指針將在n + 1個位置后面 - 只是正確的點，以便能夠跳過下一個節點。

代碼如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode(0);
        ListNode fast = start, slow = start;
        slow.next = head;
        
        for (int i = 1; i <= n+1; i++) {
            fast = fast.next;
        }
        
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        slow.next = slow.next.next;
        return start.next;
    }
}

(2)Linked List Cycle

linkedlist接口、

解題思路：

使用快慢引用的思路。兩個引用都指向鏈表頭，從鏈表頭開始遍歷，慢引用每次前進一步，而快引用每次前進兩步，如果鏈表是有環路的，那么快引用終將追上慢引用；如果沒有環路，那么遍歷就會有結束的時候

代碼如下：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public Boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }

        ListNode fast, slow;
        fast = head;
        slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow) {
                return true;
            }
        } 
        return false;
    }
}

corrupted double-linked list。(3)Remove Linked List Elements

解題思路：簡單明了，遍歷整個鏈表，遇到相應值得節點刪掉即可。

代碼如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while (head.next != null) {
            if (head.next.val == val) {
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }
        return dummy.next;
    }
}

linkedlist添加元素、(4)Intersection of Two Linked Lists

解題思路：

1，獲取兩個列表的長度。2，將它們對齊到相同的起點。3，將它們一起移動，直到找到交點，或者結束null

java ArrayList，代碼如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA);
        int lenB = length(headB);
        // move headA and headB to the same start point
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }
        while (lenA < lenB) {
            headB = headB.next;
            lenB--;
        }
        // find the intersection until end
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
        
    }
    private int length (ListNode node){
        int length = 0;
        while (node != null) {
            node = node.next;
            length++;
        }
        return length;
    }
}

?(5)Palindrome Linked List

解題思路：

找到鏈表的中間節點，把后半段的原地鏈表反轉（當然也可以反轉前半段），然后和前半段進行比較，符合題目O（1）空間復雜度的要求。

代碼如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isPalindrome(ListNode head) {
         if (head == null || head.next == null) {//0個節點或是1個節點  
             return true;  
         }
         //找到中間節點
         ListNode fast = head; 
         ListNode slow = head;  
         while (fast.next != null && fast.next.next != null)  
         {  
             fast = fast.next.next;  
             slow = slow.next;  
         }  
         //對鏈表后半段進行反轉  
         ListNode midNode = slow;  
         ListNode firNode = slow.next;//后半段鏈表的第一個節點  
         ListNode cur = firNode.next;//插入節點從第一個節點后面一個開始  
         firNode.next = null;//第一個節點最后會變最后一個節點  
         while (cur != null)  
         {  
             ListNode nextNode = cur.next;//保存下次遍歷的節點  
             cur.next = midNode.next;  
             midNode.next = cur;  
             cur = nextNode;  
         }  
           
         //反轉之后對前后半段進行比較  
         fast = midNode.next;  
         slow = head;  
         while (fast != null)  
         {  
             if (fast.val != slow.val)  
                 return false;  
             slow = slow.next;  
             fast = fast.next;  
         }  
         return true;
    }
}

?