[数据结构与算法]LeetCode第86题分割链表&&第160题相交链表

1. 方法
   双指针
2. 算法思想
   核心是使用两个指针，一个指小于x的结点，一个指大于等于x的结点。然后对原链表进行遍历。注意最后执行两步操作：小于x的结点指针指向大于等于x结点头针织；大于等于x的链表尾指针进行截断，不然容易出现环。
3. 详细代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode result = new ListNode(0);
        ListNode middle = new ListNode(0);
        ListNode resultTemp = result;
        ListNode middleTemp = middle;

        
        while(head != null){
            if(head.val >= x){
                middle.next = head;
                middle = middle.next;
            }else{
                result.next = head;
                result = result.next;
            }
            head = head.next;
        }
        //最后两步操作
        result.next = middleTemp.next;
        middle.next = null;

        return resultTemp.next;

    }
}

以下为相交链表

1. 方法
   哈希表
2. 算法思想
   特别值得注意一点是，相同数字不代表是相同的结点，相同的结点需要位置相同。这里采用hash存储，将第一个链表保存至hash表中，然后对第二个链表进行遍历，获得结果。
3. 详细代码

/**
 * 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) {
        HashMap<ListNode,Integer> map = new HashMap<ListNode,Integer>();
        int i = 0;

        while(headA != null){
            map.put(headA,i++);
            headA = headA.next;
        }
        while(headB != null){
            if(map.containsKey(headB)) return headB;
            headB = headB.next;
        }
        return null;
    }
}