206 .链表的反转

时间复杂度： O(n)
空间复杂度：O(1)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    var prev = null
    var curr = head
    while(curr !== null){
        var temp = curr.next
        curr.next = prev
        prev = curr
        curr = temp
    }
    return prev
};

92. 链表在指定区间的反转

如果将指定区间的链表完全翻转后再追加，需要考虑许多边界情况，处理比较复杂，现在考虑将逐一反转将m起始的每个元素逐一反转到m前面元素的后面

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode start0 = dummy;
        ListNode start1 = head;
        
        for(int i = 1; i < m; i++){
            start0 = start1;
            start1 = start1.next;
        }
        for(int i = 0; i < n-m; i++){
            ListNode temp = start1.next;
            start1.next = temp.next;
            temp.next = start0.next;
            start0.next = temp;
                
        }
        return dummy.next;
    }
}

160.求两个链表的交点

思路1：比较两个链表的长度，将较长的节点向后推移差值后开始遍历
思路2：设置两个指针AB，当其中一个指针走到末尾的时候从另一个指针的头节点开始遍历，直到两个指针节点相等位置，其实也是推迟较长节点的原理
时间复杂度： O（m+n）
空间复杂度： O（1）

/**
 * 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) {
        if( headA == null || headB == null) return null;
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB){
            pA = (pA != null)? pA.next: headB;
            pB = (pB != null)? pB.next: headA;
        }
        return pA;
    }
}

141. 判断是否是循环链表

思路1：逐个遍历每个节点，并在hash table中记录每个节点的引用或内存地址。如果当前节点为null，则已经到达列表的末尾，这个链表不是循环的。如果当前节点的引用在哈希表中，就返回true
时间复杂度：O（n）
空间复杂度：O（1）

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

思路2：用两个快慢指针，一个走一步，一个走两步，如果是循环链表的话两个链表最终会相遇
时间复杂度：O(n)
空间复杂度: O(1)

public class Solution {
    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;
    }
}

142. 返回链表循环开始的节点，如果没有，返回null
     思路：设定两个快慢指针，循环之外的部分长x，循环链表长y，相遇时间为t，相遇的时候两者的路程差，即，其中m为常数，走的较为慢的节点离循环节点的位置 ，所以这个长度与循环之外的长度x相等，这个时候让慢指针回到起止节点，两个指针相遇的时候即为起始节点。
     时间复杂度：O(n)
     空间复杂度：O(1)

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

86.链表划分，划分后链表的相对顺序不变

思路：用两个链表分别存储小于x的一部分，存储大于x的一部分，再将两个链表拼接
时间复杂度：O(n)
空间复杂度：O(n)
注意要把right的尾节点置空，然后要判断left与t1是否相等（为空）

class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head == null || head.next == null) return head;
        ListNode left = new ListNode(0);
        ListNode right = new ListNode(0);
        ListNode t1 = left;
        ListNode t2 = right;
        ListNode p = head;
        while(p != null){
            if(p.val < x){
                t1.next = p;
                t1 = t1.next;
            }else{
                t2.next = p;
                t2 = t2.next;
            }
            p = p.next;
        }
        t2.next = null;
        if(t1 != left){
            t1.next = right.next;
            head = left.next;
        }else{
            head = right.next;
        }
        return head;
    }
}