6/11, LinkedList 杂题

6/11, LinkedList 杂题

Intersection of Two Linked Lists

最早听到这题还是夏天实习吃饭的时候，现在也不知道那哥们都在忙啥。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode ptrA = headA;
        ListNode ptrB = headB;
        while(ptrA != null){
            ptrA = ptrA.next;
            lenA ++;
        }
        while(ptrB != null){
            ptrB = ptrB.next;
            lenB ++;
        }

        ptrA = headA;
        ptrB = headB;

        if(lenA > lenB){
            for(int i = 0; i < lenA - lenB; i++){
                ptrA = ptrA.next;
            }
        } else {
            for(int i = 0; i < lenB - lenA; i++){
                ptrB = ptrB.next;
            }
        }

        while(ptrA != ptrB){
            ptrA = ptrA.next;
            ptrB = ptrB.next;
        }

        return ptrA;
    }
}

Palindrome Linked List

O(n) 时间，O(1) 空间。好久不写链表了，感觉写的有点粗糙。。

用都指向 head 的快慢指针可以判断链表长度奇偶，最后 fast == null 的时候为偶，slow 指向后半单第一个节点；fast.next == null 的时候链表长度为奇数，slow 指向中间节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;

        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast == null){
            ListNode headB = reverse(slow);
            return compare(head, headB);
        } else {
            ListNode headB = slow.next;
            slow = null;
            headB = reverse(headB);
            return compare(head, headB);
        }

    }

    private boolean compare(ListNode headA, ListNode headB){
        while(headA != null && headB != null){
            if(headA.val != headB.val) return false;

            headA = headA.next;
            headB = headB.next;
        }
        return true;
    }

    private ListNode reverse(ListNode head){
        ListNode prev = null;
        while(head != null){
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

Remove Duplicates from Sorted List

能这样 30秒 AC 的良心水题，已经不多了=。=

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        while(head != null && head.next != null){
            if(head.val == head.next.val){
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }

        return dummy.next;
    }
}

Merge Two Sorted Lists

40 秒能 AC 的良心水题，也不多啊！

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;

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

        return dummy.next;
    }
}

Merge k Sorted Lists

在 LeetCode 早期年代，这样的题居然可以算成 Hard 难度。。

public class Solution {

    private class NodeComparator implements Comparator<ListNode>{
        public int compare(ListNode one, ListNode two){
            return one.val - two.val;
        }
    }
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;

        ListNode dummy = new ListNode(0);
        ListNode head = dummy;

        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(new NodeComparator());
        for(ListNode node : lists){
            if(node != null) heap.offer(node);
        }

        while(!heap.isEmpty()){
            ListNode node = heap.poll();
            head.next = node;
            head = head.next;

            if(node.next != null) heap.offer(node.next);
        }

        return dummy.next;

    }
}

Odd Even Linked List

拼接链表，认准多个 dummy node.

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode oddDummy = new ListNode(0);
        ListNode evenDummy = new ListNode(0);
        ListNode odd = oddDummy;
        ListNode even = evenDummy;

        boolean isOdd = true;
        while(head != null){
            if(!isOdd){
                even.next = head;
                even = even.next;
            } else {
                odd.next = head;
                odd = odd.next;
            }
            head = head.next;
            isOdd = !isOdd;
        }
        odd.next = evenDummy.next;
        even.next = null;

        return oddDummy.next;
    }
}

Swap Nodes in Pairs

一开始想复杂了，还挑着拆成两个 list .. 其实就是注意下存中间两个 node，还有这两个 node 的 prev 与 next，循环解决就行。

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        while(head != null && head.next != null){
            ListNode cur1 = head;
            ListNode cur2 = head.next;
            ListNode next = head.next.next;

            prev.next = cur2;
            cur2.next = cur1;
            cur1.next = next;

            head = next;
            prev = cur1;
        }

        return dummy.next;
    }
}