单链表

单链表由一个个节点（Node）组成，引用LeetCode里对单链表节点的表示：
<pre>
/**

• Definition for singly-linked list.
• class ListNode {
• int val;
• ListNode next;
• ListNode(int x) {

•    val = x;
  

•    next = null;
  

• }
• }
  */
  </pre>

每个节点里包含储存的内容及下一个节点的引用，这样，获得一个头结点（head），就可以对其他任意节点进行操作。

以下是一些单链表经典题，LeetCode上都有。

1.判断是否有环

可以用哈希表（HashSet）通过判重的方式解决，也可以用一快一慢两个指针来解决，这样空间复杂度只有O(1)。具体思想是，快指针每次移动2，慢指针每次移动1，如果有环，那么快指针在某个时刻会追赶上慢指针。注意初始化时要让快指针先移一格，否则最开始快慢指针就会重合。
<pre>
public boolean hasCycle(ListNode head) {

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

那么环从哪里开始呢？假设慢指针从头结点到环起始处需要走A步，再走B步与快指针相遇。此时快指针走了2A+2B比慢指针多走一圈N，2A + 2B = N + A + B。
由此得出 N = A + B。
慢指针已经走了一圈中的B，再走A步又回到环起始处，而A正是从头结点到环起始处的步数，用另一个指针从头结点开始与慢指针同步走，相遇处即为环起始处。
<pre>

public ListNode detectCycle(ListNode head) {
    
    if(head == null) return null;
    
    ListNode slow = head;
    ListNode fast = head;
    
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        
        if(slow == fast){
            ListNode start = head;
            while(start != slow){
                start = start.next;
                slow = slow.next;
            }
            return start;
        }
    }
    
    return null;
    
}

</pre>

</br>

2.反转链表

设置前后两个指针，每次让后指针的next指向前指针，然后两个指针都往后挪一位。注意前指针应初始化为null，应设置一个临时变量储存后指针的后一位以支持挪动。
<pre>
public ListNode reverseList(ListNode head) {

    ListNode pre = null;
    ListNode curr = head;
     
    while(curr != null){
        ListNode next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    
    return pre;
}

</pre>

</br>

3.合并两个有序单链表

实现思想就是用small，big两个指针来分别指向两个链表中当前节点值较小和较大的，如果small的下一个节点比big大了，就把small的next指向big，然后big指向原先的small链表元素。
<pre>
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

    if(l1 == null) return l2;
    if(l2 == null) return l1;
    
    ListNode small = null;
    ListNode big = null;
    
    if(l1.val > l2.val){
        small = l2;
        big = l1;
    }else{
        small = l1;
        big = l2;
    }
    
    ListNode head = small;
    
    while(small.next != null && big != null){
        if(small.next.val > big.val){
            ListNode temp = small.next;
            small.next = big;
            small = big;
            big = temp;
        }else{
            small = small.next;
        }
        
    }
    
    small.next = big;
    
    return head;        
    
}

</pre>
看了下LeetCode其他人答案发现还可以递归解决，于是顺手也写了个，确实简洁不少。
<pre>
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;

    ListNode head = null;
    
    if(l1.val < l2.val){
        head = l1;
        head.next = mergeTwoLists(l1.next,l2);
    }else{
        head = l2;
        head.next = mergeTwoLists(l1,l2.next);
    }
    
    return head;   
}

</pre>