LC Linked List (Java)

LC 链表经典题目总结，此篇包含五题：

• 021 - Merge 2 Sorted Lists
• 083 - Remove Duplicates from Sorted List
• 206 - Reverse Linked List
• 234 - Palindrome Linked List
• 141 - Linked List Cycle

Merge 2 Sorted Lists

Singly linked list. 用题中给的 class 就行，不需要用 Java 的 LinkedList.

public ListNode merge(ListNode l1, ListNode l2) {
    
    // 用了 dummy，就不需要判断 l1, l2 是否为空
    // 因为 dummy 始终指向一个哨兵节点
    ListNode dummy = new ListNode(0);			
    ListNode cur = dummy;						
    
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            cur.next = l1;
            l1 = l1.next;
        }
        else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = (l1 == null) ? l2 : l1;		// 三目运算符
    return dummy.next;
}

Remove Duplicates from Sorted List

模板题

public ListNode deleteDuplicates(ListNode head) {
    ListNode cur = head;
    
    while (cur != null && cur.next != null) {
        if (cur.val == cur.next.val)
            cur.next = cur.next.next;
        
        // else 不要忘了，否则： [1, 1, 1] -> [1, 1]
        else cur = cur.next;										
    }
    return head;
}

Reverse Linked List

经典模板题

public ListNode reverseList(ListNode head) {
    if(head == null || head.next == null)  return head;						
    
    // pre 这个相当于 New Head
    ListNode pre = null;		
    
    // 如果 head == null，那就说明链表到头了
    while (head != null) {		
        
        // 先用 tmp 储存 next，然后让 next 指向之前的 node
        ListNode tmp = head.next;	
        head.next = pre;   
        pre = head;
        head = tmp;		
    }					   
    return pre;			   
}						

Palindrome Linked List

画图。此题要在熟练 reverse linked list 的基础之上

分为三块：reverse，一行判断奇偶， slow & pre 遍历

public boolean isPalindrome(ListNode head) {

    if (head == null || head.next == null) return true;

    // 核心在于，用两个指针，slow 一边走，一边 reverse
    ListNode fast = head;			
    ListNode slow = head;		
    ListNode pre = null;

    while (fast != null && fast.next != null) {		// fast 的判断

        fast = fast.next.next;

        // 下面四行为 reverse link 的基本操作
        ListNode tmp = slow.next;					
        slow.next = pre;							
        pre = slow;
        slow = tmp;
    }

    // 如果长度为奇数 （那么slow再移一格，跳过中间的那个点）
    if (fast != null)   slow = slow.next;			

    // pre is the New Head
    while (pre != null) {	// 用 (slow != null) 一样的      						
        if (slow.val != pre.val) return false;		
        slow = slow.next;
        pre = pre.next;
    }
    return true;
}

拓展： 链表找倒数第k个节点

创建两个指针，第一个先走k-1步然后两个在一同走。第一个走到最后时则第二个指针指向倒数第k位置。

Linked List Cycle

public boolean hasCycle(ListNode head) {
    
    if (head == null || head.next == null) return false;

    // 直接用 head 也可以，但用 cur 指代好一点
    // 经典思想： 两个指针，如果有循环，那么总会碰面的
    ListNode cur = head;			
    ListNode fast = cur;			
    ListNode slow = cur;

    // 注意这里的条件判断，fast.next 必须不是 null 才能进行下去
    // fast.next.next 可以是 null （到了链尾）	
    while (fast != null && fast.next != null) {										
        fast = fast.next.next;
        slow = slow.next;
        
        // 先移动指针，再判断，顺序不可颠倒
        if (fast == slow) return true;				
    }

    return false;    
        
}