链表相关题目

简单题

判断一个链表中是否有环

快慢指针法
设置两个指针，一个指针每次走两步，另一个每次走一步，若两者相遇，则必然存在环。

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

合并两个有序链表

head tail指针
设置头尾指针，头指针作为返回的头节点，尾指针作为每次向链表中添加的节点

1. 找两个链表中较小的头节点作为新链表的头节点head；tail指向head
2. 依次比较两个链表中未合并部分的头（L1 L2），并将较小者连接到tail后面。tail后移
3. 处理剩余的节点。（直接连接过来即可）

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        ListNode temp;
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode head = l1.val < l2.val ? l1 : l2;
        ListNode tail = head;
        l1 = (head == l1)? l1.next:l1;
        l2 = (head == l2) ? l2.next:l2;

        while(l1!=null && l2!=null){
            if(l1.val<=l2.val) {tail.next = l1; l1=l1.next;}
            else {tail.next = l2; l2 = l2.next;}
            tail = tail.next;
        }
        tail.next = l1==null? l2: l1;

        return head;

    }
}

此外，本题还可以用递归法解决

        public ListNode mergeTwoLists(ListNode linked1, ListNode linked2) {
        //只要有一个为空，就返回另一个
        if (linked1 == null || linked2 == null)
            return linked2 == null ? linked1 : linked2;
        //把小的赋值给first
        ListNode first = (linked2.val < linked1.val) ? linked2 : linked1;
        //当前头的下一个节点，与另一个链表的节点比较
        first.next = mergeTwoLists(first.next, first == linked1 ? linked2 : linked1);
        return first;
    }