# 6/11, LinkedList 杂题

## 6/11, LinkedList 杂题

## [Intersection of Two Linked Lists](https://leetcode.com/problems/intersection-of-two-linked-lists/)

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

```java
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](https://leetcode.com/problems/palindrome-linked-list/)

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

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

```java
/**
 * 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 ](https://github.com/mnmunknown/algorithm-notes/tree/3c03c403dea353c29bf5dc55966e338f3385a7ed/Remove%20Duplicates%20from%20Sorted%20List/README.md)

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

```java
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](https://leetcode.com/problems/merge-two-sorted-lists/)

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

```java
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](https://leetcode.com/problems/merge-k-sorted-lists/)

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

```java
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](https://leetcode.com/problems/odd-even-linked-list/)

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

```java
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](https://leetcode.com/problems/swap-nodes-in-pairs/)

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

```java
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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/linkedlistff0c_lian_biao/611-_linkedlist_za_ti.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.