# Table of Contents

- [Linked List Cycle | LintCode & LeetCode](#linked-list-cycle-lintcode-leetcode)
- [Add Two Numbers II | LintCode & LeetCode](#add-two-numbers-ii-lintcode-leetcode)
- [Add Two Numbers | LintCode & LeetCode](#add-two-numbers-lintcode-leetcode)
- [Odd Even Linked List | LintCode & LeetCode](#odd-even-linked-list-lintcode-leetcode)
- [Intersection of Two Linked Lists | LintCode & LeetCode](#intersection-of-two-linked-lists-lintcode-leetcode)
- [Reverse Linked List | LintCode & LeetCode](#reverse-linked-list-lintcode-leetcode)
- [Remove Linked List Elements | LintCode & LeetCode](#remove-linked-list-elements-lintcode-leetcode)
- [Remove Nth Node From End of List | LintCode & LeetCode](#remove-nth-node-from-end-of-list-lintcode-leetcode)
- [Merge Two Sorted Lists | LintCode & LeetCode](#merge-two-sorted-lists-lintcode-leetcode)
- [Sort List | LintCode & LeetCode](#sort-list-lintcode-leetcode)
- [Merge k Sorted Lists | LintCode & LeetCode](#merge-k-sorted-lists-lintcode-leetcode)
- [Reverse Linked List II | LintCode & LeetCode](#reverse-linked-list-ii-lintcode-leetcode)
- [Design Doubly Linked List | LintCode & LeetCode](#design-doubly-linked-list-lintcode-leetcode)

---

# Linked List Cycle | LintCode & LeetCode

[](#question)

Question


---------------------------

[leetcode: Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)
 [lintcode: Linked List Cycle](http://www.lintcode.com/en/problem/linked-list-cycle/)

Copy

    Given a linked list, determine if it has a cycle in it.
    
    Follow up:
    Can you solve it without using extra space?

[](#ti-jie-si-lu)

题解思路


---------------------------

链表中的Two Pointers是一种很常用的思想，快慢两个指针，通过是否相遇，来判断链表中是否有环。相比于用HashMap的方法，优点是空间复杂度仅为O(1)，时间复杂度O(n)。

参考 LeetCode: [https://leetcode.com/articles/linked-list-cycle/](https://leetcode.com/articles/linked-list-cycle/)

[](#yuan-dai-ma)

源代码


-------------------------

Copy

    /**
     * Definition for ListNode.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int val) {
     *         this.val = val;
     *         this.next = null;
     *     }
     * }
     */
    
    public class Solution {
        public boolean hasCycle(ListNode head) {
            if (head == null || head.next == null) {
                return false;
            }
            ListNode slow = head;
            ListNode fast = head.next;
            while (slow != fast) {
                if (fast == null || fast.next == null) {
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }
    }

[PreviousMerge k Sorted Lists](/lintcode/linked_list/merge_k_sorted_lists)
[NextLinked List Cycle II](/lintcode/linked_list/linked_list_cycle_ii)

Last updated 4 years ago

Was this helpful?

---

# Add Two Numbers II | LintCode & LeetCode

[](#question)

Question


---------------------------

> You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in forward order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
> 
> Example:
> 
> Given 6->1->7 + 2->9->5. That is, 617 + 295.
> 
> Return 9->1->2. That is, 912.

[](#analysis)

Analysis


---------------------------

相比于数字为倒序的链表相加问题(add two numbers)，顺序的数字（单向）链表存在处理进位的问题，因为没有反向指针，所以后节点所得的进位，难以加到前一个节点上。 此外，与 add two numbers 问题一样，不能简单地将链表转为整形int或长整型long，因为很有可能超出范围，使用链表的好处正是在于可以几乎无限制地增加number的位数，如果有转换的过程，则很有可能丢失精度。

因此，最简单的解决办法，就是将 add two numbers ii 问题，转化为 add two numbers 问题：先分别对每个number链表进行反转，然后进行相加，最后将所得链表再进行反转。

复杂问题可以通过分析，转化和分解为更小的，更基础的问题。

[](#solution)

Solution


---------------------------

Copy

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
    
        public ListNode reverse(ListNode head) {
            ListNode prev = null;
            while (head != null) {
                ListNode next = head.next;
                head.next = prev;
                prev = head;
                head = next;
            }
            return prev;
        }
    
        public ListNode addLists(ListNode l1, ListNode l2) {
            if (l1 == null && l2 == null) {
                return null;
            }
    
            ListNode head = new ListNode(0);
            ListNode pointer = head;
    
            int carry = 0;
    
            while (l1 != null && l2 != null) {
    
                int sum = l1.val + l2.val + carry;
                carry = sum / 10;
    
                pointer.next = new ListNode(sum % 10);
                pointer = pointer.next;
                l1 = l1.next;
                l2 = l2.next;
            }
    
            while (l1 != null) {
                int sum = l1.val + carry;
                carry = sum / 10;
                pointer.next = new ListNode(sum % 10);
                pointer = pointer.next;
                l1 = l1.next;
            }
    
            while (l2 != null) {
                int sum = l2.val + carry;
                carry = sum / 10;
                pointer.next = new ListNode(sum = sum % 10);
                pointer = pointer.next;
                l2 = l2.next;
            }
    
            if (carry != 0) {
                pointer.next = new ListNode(carry);
            }
    
            return head.next;
        }
        /**
         * @param l1: the first list
         * @param l2: the second list
         * @return: the sum list of l1 and l2
         */
        public ListNode addLists2(ListNode l1, ListNode l2) {
            l1 = reverse(l1);
            l2 = reverse(l2);
    
            return reverse(addLists(l1, l2));
        }
    }

[PreviousLinked List Cycle II](/lintcode/linked_list/linked_list_cycle_ii)
[NextAdd Two Numbers](/lintcode/linked_list/add-two-numbers)

Last updated 4 years ago

Was this helpful?

---

# Add Two Numbers | LintCode & LeetCode

You are given two **non-empty** linked lists representing two non-negative integers. The digits are stored in **reverse order** and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

**Example:**

Copy

    Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
    Output: 7 -> 0 -> 8
    Explanation: 342 + 465 = 807.

[](#analysis)

Analysis


---------------------------

Refer to [https://leetcode.com/problems/add-two-numbers/solution/](https://leetcode.com/problems/add-two-numbers/solution/)

[](#solution)

Solution


---------------------------

Copy

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode dummyHead = new ListNode(0);
            ListNode p = l1, q = l2, curr = dummyHead;
            int carry = 0;
            while (p != null || q != null) {
                int x = (p != null) ? p.val : 0;
                int y = (q != null) ? q.val : 0;
                int sum = carry + x + y;
                carry = sum / 10;
                curr.next = new ListNode(sum % 10);
                curr = curr.next;
                if (p != null) p = p.next;
                if (q != null) q = q.next;
            }
            if (carry > 0) {
                curr.next = new ListNode(carry);
            }
            return dummyHead.next;
        }
    }

[PreviousAdd Two Numbers II](/lintcode/linked_list/add_two_numbers_ii)
[NextOdd Even Linked List](/lintcode/linked_list/odd-even-linked-list)

Last updated 4 years ago

Was this helpful?

---

# Odd Even Linked List | LintCode & LeetCode

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in `O(1)` space complexity and `O(nodes)` time complexity.

**Example 1:**

Copy

    Input: 1->2->3->4->5->NULL
    Output: 1->3->5->2->4->NULL

**Example 2:**

Copy

    Input: 2->1->3->5->6->4->7->NULL
    Output: 2->3->6->7->1->5->4->NULL

**Note:**

The relative order inside both the even and odd groups should remain as it was in the input.

The first node is considered odd, the second node even and so on ...

[](#analysis)

Analysis


---------------------------

Copy

    Input: 1->2->3->4->5->NULL

`head -> 1`

Init `odd = head, even = head.next`, i.e. `odd -> 1, even -> 2`

Loop `odd = odd.next, even = odd.next`

Check `even != null && even.next != null`

[](#solution)

Solution


---------------------------

Copy

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode oddEvenList(ListNode head) {
            ListNode pOdd = new ListNode(0);
            ListNode pEven = new ListNode(0);
            ListNode p = head;
            ListNode p1 = pOdd;
            ListNode p2 = pEven;
            if (head == null || head.next == null) {
                return head;
            }
            while (p != null) {
                pOdd.next = p;
                pOdd = pOdd.next;
                if (p.next != null) {
                    pEven.next = p.next;
                    pEven = pEven.next;
                    p = p.next.next;
                } else {
                    pEven.next = null;
                    break;
                }
            }
            pOdd.next = p2.next;
            return p1.next;
        }
    }

Simplified Version

Copy

    public class Solution {
        public ListNode oddEvenList(ListNode head) {
            if (head != null) {
    
                ListNode odd = head, even = head.next, evenHead = even;
    
                while (even != null && even.next != null) {
                    odd.next = odd.next.next;
                    even.next = even.next.next;
                    odd = odd.next;
                    even = even.next;
                }
                odd.next = evenHead;
            }
            return head;
        }
    }

Both have O(1) space complexity and O(nodes) time complexity

[PreviousAdd Two Numbers](/lintcode/linked_list/add-two-numbers)
[NextIntersection of Two Linked Lists](/lintcode/linked_list/intersection-of-two-linked-lists)

Last updated 4 years ago

Was this helpful?

---

# Intersection of Two Linked Lists | LintCode & LeetCode

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

Copy

    A:          a1 → a2
                       ↘
                         c1 → c2 → c3
                       ↗            
    B:     b1 → b2 → b3

begin to intersect at node c1.

**Notes:**

*   If the two linked lists have no intersection at all, return `null`
    
*   The linked lists must retain their original structure after the function returns.
    
*   You may assume there are no cycles anywhere in the entire linked structure.
    
*   Your code should preferably run in O(n) time and use only O(1) memory.
    

[](#analysis)

Analysis


---------------------------

[https://leetcode.com/problems/intersection-of-two-linked-lists/solution/](https://leetcode.com/problems/intersection-of-two-linked-lists/solution/)

This problem at first doesn't appear to be hard, and it's easy to come up with Brute Force or Hash Table approaches.

But what's really fascinating is coming up with an idea of combining two linked list in order to make use of **Two Pointers** technique.

### 

[](#approach-1-brute-force)

Approach 1: Brute Force

For each node `ai` in list A, traverse the entire list B and check if any node in list B coincides with `ai`.

**Complexity Analysis**

*   Time complexity : O(mn).
    
*   Space complexity : O(1).
    

### 

[](#approach-2-hash-table)

Approach 2: Hash Table

Traverse list A and store the address / reference to each node in a hash set. Then check every node `bi` in list B: if `bi` appears in the hash set, then `bi`is the intersection node.

**Complexity Analysis**

*   Time complexity :O(m+n).
    
*   Space complexity :O(m) or O(n).
    

### 

[](#approach-3-two-pointers)

**Approach 3: Two Pointers**

Maintain two pointers pA and pB initialized at the head of A and B, respectively. Then let them both traverse through the lists, one node at a time.

When pA reaches the end of a list, then redirect it to the head of B (yes, B, that's right.); similarly when pB reaches the end of a list, redirect it the head of A.

If at any point pA meets pB, then pA/pB is the intersection node.

To see why the above trick would work, consider the following two lists: A = {1,3,5,7,9,11} and B = {2,4,9,11}, which are intersected at node '9'. Since B.length (=4) < A.length (=6), pB would reach the end of the merged list first, because pB traverses exactly 2 nodes less than pA does. By redirecting pB to head A, and pA to head B, we now ask pB to travel exactly 2 more nodes than pA would. So in the second iteration, they are guaranteed to reach the intersection node at the same time.

If two lists have intersection, then their last nodes must be the same one. So when pA/pB reaches the end of a list, record the last element of A/B respectively. If the two last elements are not the same one, then the two lists have no intersections.

**Complexity Analysis**

*   Time complexity : O(m+n).
    
*   Space complexity : O(1).
    

A，B两个linked list分别出发，遇到链表末尾后转而指向另一条链表继续遍历，那么当它们相遇时，正好是两条链表的相交点。即使没有相交点，两个指针最终也将同时指向null，这时也满足pointerA == pointerB.

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!](https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!)

**Here's another nice visualization of this solution:**

[https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!/165648](https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!/165648)

[](#solution)

Solution


---------------------------

Two Pointers - O(n) time, O(1) space

Copy

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            ListNode p = headA;
            ListNode q = headB;
            while (p != q) {
                p =  (p != null) ? p.next : headB;
                q =  (q != null) ? q.next : headA;
            }
            return p;
        }
    }

[PreviousOdd Even Linked List](/lintcode/linked_list/odd-even-linked-list)
[NextReverse Linked List](/lintcode/linked_list/reverse-linked-list)

Last updated 4 years ago

Was this helpful?

![](https://aaronice.gitbook.io/~gitbook/image?url=https%3A%2F%2F1611446478-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-M63nDeIUEfibnkE8C6W%252Fsync%252Fb55edb5b20a27e7b685ccc0c661d6db42cc20457.jpg%3Fgeneration%3D1588144784004708%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=bcb15e13&sv=2)

---

# Reverse Linked List | LintCode & LeetCode

Reverse a singly linked list.

**Example:**

Copy

    Input: 1->2->3->4->5->NULL
    Output: 5->4->3->2->1->NULL

[](#solution)

Solution


---------------------------

### 

[](#iterative)

iterative

Copy

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

Copy

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

### 

[](#recursive)

recursive

Copy

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }

Copy

        ListNode newHead;
        public ListNode reverseList(ListNode head) {
            if (head == null) {
                return null;
            }
            return reverseUtil(head, null);
        }
        ListNode reverseUtil(ListNode curr, ListNode prev) { 
    
            /* If last node mark it head*/
            if (curr.next == null) { 
                newHead = curr; 
    
                /* Update next to prev node */
                curr.next = prev; 
    
                return newHead; 
            } 
    
            /* Save curr->next node for recursive call */
            ListNode next = curr.next; 
    
            /* and update next ..*/
            curr.next = prev; 
    
            reverseUtil(next, curr); 
            return newHead; 
        }

**Reference Code**

Copy

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode reverseList(ListNode head) {
            if (head == null) {
                return head;
            }
            ListNode currentHead = head;
            while (head.next != null) {
                ListNode p = head.next;
                head.next = p.next;
                p.next = currentHead;
                currentHead = p;
            }
            return currentHead;
        }
    }

Using Dummy Node Version

Copy

    class Solution {
        public ListNode reverseList(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode dummy = new ListNode(0);
            ListNode p = head;
            dummy.next = head;
            while (p.next != null) {
                ListNode q = p.next;
                p.next = q.next;
                q.next = dummy.next;
                dummy.next = q;
            }
            return dummy.next;
        }
    }

[PreviousIntersection of Two Linked Lists](/lintcode/linked_list/intersection-of-two-linked-lists)
[NextReverse Linked List II](/lintcode/linked_list/reverse-linked-list-ii)

Last updated 4 years ago

Was this helpful?

---

# Remove Linked List Elements | LintCode & LeetCode

Remove all elements from a linked list of integers that have value**val**.

**Example:**

Copy

    Input: 1->2->6->3->4->5->6, val = 6 
    Output: 1->2->3->4->5

[](#analysis)

Analysis


---------------------------

需要记录prev指针方便找到val时移除当前节点

[](#solution)

Solution


---------------------------

Copy

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode removeElements(ListNode head, int val) {
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode curr = head;
            ListNode prev = dummy;
            while (curr != null) {
               if (curr.val == val) {
                    prev.next = curr.next; 
               } else {
                    prev = prev.next;
               }  
               curr = curr.next;
            }
            return dummy.next;
        }
    }

[PreviousReverse Linked List II](/lintcode/linked_list/reverse-linked-list-ii)
[NextRemove Nth Node From End of List](/lintcode/linked_list/remove-nth-node-from-end-of-list)

Last updated 4 years ago

Was this helpful?

---

# Remove Nth Node From End of List | LintCode & LeetCode

Given a linked list, remove the _n_\-th node from the end of list and return its head.

**Example:**

Copy

    Given linked list: 1->2->3->4->5, and n = 2.
    
    After removing the second node from the end, the linked list becomes 1->2->3->5.

**Note:**

Given \_n \_will always be valid.

**Follow up:**

Could you do this in one pass?

[](#analysis)

Analysis


---------------------------

**Reference**: [https://leetcode.com/problems/remove-nth-node-from-end-of-list/solution/](https://leetcode.com/articles/remove-nth-node-from-end-of-list/)

### 

[](#two-pass)

Two Pass:

Intuition: Remove the `(L - n + 1) th` node from the beginning in the list , where `L` is the list length. This problem is easy to solve once we found list length `L`.

In the second pass, relink the `next` of `(L - n)` th node to the `(L - n + 2)` the node

**Complexity Analysis**

*   Time complexity :O(L)O(L).
    
    The algorithm makes two traversal of the list, first to calculate list length L and second to find the (L−n) th node. There are 2L- n operations and time complexity isO(L).
    
*   Space complexity :O(1).
    
    We only used constant extra space.
    

### 

[](#one-pass)

One Pass:

Using two pointers, which the first and second pointers are exactly separated by `n` nodes apart, and maintain the constant gap between the two pointers while advancing both of them.

保持一定的距离两个相同速度的pointer，当前方的pointer p1到达末尾时，后方的pointer p2正好是我们需要删除的元素位置的左侧（i - 1）。因为这里是删除操作，因此后方的pointer做一个常规的删除下一个节点的操作即可p2.next = p2.next.next。

**Complexity Analysis**

*   Time complexity :O(L).
    
    The algorithm makes one traversal of the list of L nodes. Therefore time complexity is O(L).
    
*   Space complexity :O(1).
    
    We only used constant extra space.
    

[](#solution)

Solution


---------------------------

Two Pass: get length first, then iterate to the node in second pass

Copy

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            int length = getLengthOfList(head);
            System.out.println("Length: " + length);
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode prev = dummy;
            for (int i = 0; i < length - n; i++) {
                prev = prev.next;
            }
            prev.next = prev.next.next;
            return dummy.next;
        }
        public int getLengthOfList(ListNode head) {
            int length = 0;
            while (head != null) {
                length++;
                head = head.next;
            }
            return length;
        }
    }

One Pass: Using two pointers, which first pointer is n nodes ahead of second pointer

Copy

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        // Advances first pointer so that the gap between first and second is n nodes apart
        for (int i = 1; i <= n + 1; i++) {
            first = first.next;
        }
        // Move first to the end, maintaining the gap
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

**Two Pointers - Java Preferred Implementation:**

Copy

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode p1, p2;
            ListNode dummy = new ListNode(0);    
            dummy.next = head;
            p1 = head;
            p2 = dummy;
            for (int i = 0; i < n; i++) {
                p1 = p1.next;
            }
            while (p1 != null) {
                p1 = p1.next;
                p2 = p2.next;
            }
            p2.next = p2.next.next;
            return dummy.next;
        }
    }

[PreviousRemove Linked List Elements](/lintcode/linked_list/remove-linked-list-elements)
[NextMiddle of the Linked List](/lintcode/linked_list/middle-of-the-linked-list)

Last updated 4 years ago

Was this helpful?

---

# Merge Two Sorted Lists | LintCode & LeetCode

`Linked List`

Easy

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

**Example:**

Copy

    Input: 1->2->4, 1->3->4
    Output: 1->1->2->3->4->4

[](#solution)

Solution


---------------------------

### 

[](#iteration)

Iteration

Time complexity : O(n+m)

Space complexity : O(1)

Copy

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(0);
            ListNode p = dummy;
            while (l1 != null || l2 != null) {
                if (l1 == null) {
                    p.next = l2;
                    break;
                }
                if (l2 == null) {
                    p.next = l1;
                    break;
                }
                if (l1.val < l2.val) {
                    p.next = l1;
                    l1 = l1.next;
                } else {
                    p.next = l2;
                    l2 = l2.next;
                }
                p = p.next;
            }
            return dummy.next;
        }
    }

### 

[](#leetcode-official-iteration)

LeetCode Official - Iteration

Time complexity : O(n+m)

Space complexity : O(1)

Copy

    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            // maintain an unchanging reference to node ahead of the return node.
            ListNode prehead = new ListNode(-1);
    
            ListNode prev = prehead;
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    prev.next = l1;
                    l1 = l1.next;
                } else {
                    prev.next = l2;
                    l2 = l2.next;
                }
                prev = prev.next;
            }
    
            // exactly one of l1 and l2 can be non-null at this point, so connect
            // the non-null list to the end of the merged list.
            prev.next = l1 == null ? l2 : l1;
    
            return prehead.next;
        }
    }

### 

[](#leetcode-official-recursion)

LeetCode Official - Recursion

Time complexity : O(n+m)

Space complexity : O(n+m) - The first call to mergeTwoLists does not return until the ends of both l1 and l2 have been reached, so n+m stack frames consume O(n+m) space.

Copy

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

[](#reference)

Reference


-----------------------------

[https://leetcode.com/problems/merge-two-sorted-lists/solution/](https://leetcode.com/problems/merge-two-sorted-lists/solution/)

[PreviousSort List](/lintcode/linked_list/sort_list)
[NextMerge k Sorted Lists](/lintcode/linked_list/merge_k_sorted_lists)

Last updated 4 years ago

Was this helpful?

---

# Sort List | LintCode & LeetCode

[](#sort-list)

Sort List


-----------------------------

Question

[Leetcode: Sort List | LeetCode OJ](https://leetcode.com/problems/sort-list/)
 [Lintcode: (98) Sort List](http://www.lintcode.com/en/problem/sort-list/)

Copy

    Sort a linked list in O(n log n) time using constant space complexity.

[](#ti-jie-si-lu)

题解思路


---------------------------

链表的排序操作，对于常用的排序算法，能达到O(nlogn)的复杂度有快速排序(平均情况)，归并排序，堆排序。

对于数组，归并排序一般需要使用O(n)的额外空间，虽然也有原地的实现方法。但对于链表这样的数据结构，排序是指针next值的变化，所以只需要常数级的额外空间。

归并排序的核心思想在于，根据分治思想，可以按照左、右、合并的顺序，实现递归模型，也就是先找出左右链表，最后进行归并。

**三个主要步骤**

1.  **找到链表中点**：可以通过快慢指针的方法
    
2.  **合并两个有序链表**：链表的基本问题
    
3.  **分治递归**
    

[](#yuan-dai-ma)

源代码


-------------------------

Copy

    /**
     * Definition for ListNode.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int val) {
     *         this.val = val;
     *         this.next = null;
     *     }
     * }
     */
    
    public class Solution {
        private ListNode findMiddle(ListNode head) {
            ListNode slow = head;
            ListNode fast = head.next;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
    
        private ListNode merge(ListNode head1, ListNode head2) {
            ListNode dummy = new ListNode(0);
            ListNode pointer = dummy;
    
            while (head1 != null && head2 != null) {
                if (head1.val < head2.val) {
                    pointer.next = head1;
                    head1 = head1.next;
                } else {
                    pointer.next = head2;
                    head2 = head2.next;
                }
                pointer = pointer.next;
            }
    
            if (head1 != null) {
                pointer.next = head1;
            } else {
                pointer.next = head2;
            }
    
            return dummy.next;
        }
    
        /**
         * @param head: The head of linked list.
         * @return: You should return the head of the sorted linked list,
                        using constant space complexity.
         */
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode mid = findMiddle(head);
            ListNode right = sortList(mid.next);
            mid.next = null;
            ListNode left = sortList(head);
    
            return merge(left, right);
        }
    }

[PreviousLinked List](/lintcode/linked_list)
[NextMerge Two Sorted Lists](/lintcode/linked_list/merge-two-sorted-lists)

Last updated 4 years ago

Was this helpful?

---

# Merge k Sorted Lists | LintCode & LeetCode

[](#merge-k-sorted-lists)

Merge k Sorted Lists


---------------------------------------------------

`Heap`

### 

[](#description)

Description

[Leetcode: Merge k Sorted Lists | LeetCode OJ](https://leetcode.com/problems/merge-k-sorted-lists/)
 [Lintcode: Merge k Sorted Lists](http://www.lintcode.com/en/problem/merge-k-sorted-lists/)

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

### 

[](#example)

Example

Example 1

Copy

    Input:   [2->4->null, null, -1->null]
    Output:  -1->2->4->null

Example 2

Copy

    Input: [2->6->null, 5->null, 7->null]
    Output: 2->5->6->7->null

Example 3

Copy

    Input:
    [\
      1->4->5,\
      1->3->4,\
      2->6\
    ]
    Output: 1->1->2->3->4->4->5->6

[](#ti-jie-si-lu)

题解思路


---------------------------

归并k个已排序链表，可以分解问题拆解成为，重复k次，归并2个已排序链表。不过这种方法会在LeetCode中TLE（超出时间限制）。总共需要k次merge two sorted lists的合并过程。

**改进方法：**

1.  使用merge sort中的二分的思维，将包含k个链表的列表逐次分成两个部分，再逐次对两个链表合并，这样就有 log(k)次合并过程，每次均使用merge two sorted lists的算法。时间复杂度O(nlog(k))，不需要额外空间，因此空间复杂度O(1)。
    
2.  使用Priority Queues。这样保持每次取出的节点中是当前最小的，依次加入新的链表，从而得到合并的结果。时间复杂度O(nlogk)，空间复杂度O(k) 是PriorityQueue的空间。
    

[](#yuan-dai-ma)

源代码


-------------------------

*   **Divide and Conquer**
    

Copy

    /**
     * Definition for ListNode.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int val) {
     *         this.val = val;
     *         this.next = null;
     *     }
     * }
     */
    public class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(0);
            ListNode lastNode = dummy;
    
            while (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    lastNode.next = l1;
                    l1 = l1.next;
                } else {
                    lastNode.next = l2;
                    l2 = l2.next;
                }
                lastNode = lastNode.next;
            }
    
            if (l1 != null) {
                lastNode.next = l1;
            } else {
                lastNode.next = l2;
            }
    
            return dummy.next;
        }
        /**
         * @param lists: a list of ListNode
         * @return: The head of one sorted list.
         */
        public ListNode mergeKListsNaive(List<ListNode> lists) {
            if (lists == null || lists.size() == 0) {
                return null;
            }
            if (lists.size() == 1) {
                return lists.get(0);
            }
    
            int listSize = lists.size();
    
            ListNode base = lists.get(0);
    
            for (int i = 1; i < listSize; i++) {
                base = mergeTwoLists(base, lists.get(i));
            }
            return base;
        }
        /**
         * @param lists: a list of ListNode
         * @return: The head of one sorted list.
         */
         public ListNode mergeKLists(List<ListNode> lists) {
             if (lists.size() == 0) {
                 return null;
             }
             if (lists.size() == 1) {
                 return lists.get(0);
             }
             if (lists.size() == 2) {
                 return mergeTwoLists(lists.get(0), lists.get(1));
             }
             return mergeTwoLists(
                mergeKLists(lists.subList(0, lists.size()/2)),
                mergeKLists(lists.subList(lists.size()/2, lists.size()))
             );
         }
    }

*   **Divide & Conquer Another implementation**
    

Copy

    public class Solution {
        /**
         * @param lists: a list of ListNode
         * @return: The head of one sorted list.
         */
        public ListNode mergeKLists(List<ListNode> lists) {
            if (lists.size() == 0) {
                return null;
            }
            return mergeHelper(lists, 0, lists.size() - 1);
        }
    
        private ListNode mergeHelper(List<ListNode> lists, int start, int end) {
            if (start == end) {
                return lists.get(start);
            }
    
            int mid = start + (end - start) / 2;
            ListNode left = mergeHelper(lists, start, mid);
            ListNode right = mergeHelper(lists, mid + 1, end);
            return mergeTwoLists(left, right);
        }
    
        private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummy = new ListNode(0);
            ListNode tail = dummy;
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    tail.next = list1;
                    tail = list1;
                    list1 = list1.next;
                } else {
                    tail.next = list2;
                    tail = list2;
                    list2 = list2.next;
                }
            }
            if (list1 != null) {
                tail.next = list1;
            } else {
                tail.next = list2;
            }
    
            return dummy.next;
        }
    }

*   **Heap\***
    

Copy

    public class Solution {
        private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
            public int compare(ListNode left, ListNode right) {
                if (left == null) {
                    return 1;
                } else if (right == null) {
                    return -1;
                }
                return left.val - right.val;
            }
        };
    
        public ListNode mergeKLists(ArrayList<ListNode> lists) {
            if (lists == null || lists.size() == 0) {
                return null;
            }
    
            Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), ListNodeComparator);
            for (int i = 0; i < lists.size(); i++) {
                if (lists.get(i) != null) {
                    heap.add(lists.get(i));
                }
            }
    
            ListNode dummy = new ListNode(0);
            ListNode tail = dummy;
            while (!heap.isEmpty()) {
                ListNode head = heap.poll();
                tail.next = head;
                tail = head;
                if (head.next != null) {
                    heap.add(head.next);
                }
            }
            return dummy.next;
        }
    }

[PreviousMerge Two Sorted Lists](/lintcode/linked_list/merge-two-sorted-lists)
[NextLinked List Cycle](/lintcode/linked_list/linked_list_cycle)

Last updated 4 years ago

Was this helpful?

---

# Reverse Linked List II | LintCode & LeetCode

Reverse a linked list from position _m \_to \_n_. Do it in one-pass.

**Note:** 1 ≤_m_≤_n_≤ length of list.

**Example:**

Copy

    Input: 1->2->3->4->5->NULL, m = 2, n = 4
    Output: 1->4->3->2->5->NULL

[](#solution)

Solution


---------------------------

Copy

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode reverseBetween(ListNode head, int m, int n) {
            if (head == null || head.next == null || m >= n) {
               return head; 
            }
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            head = dummy;
            for (int i = 1; i < m; i++) {
                if (head == null) {
                    return null;
                }
                head = head.next;
            } 
            ListNode prevNode = head;
            ListNode tailNode = head.next;
            ListNode curr = head.next;
            prevNode.next = null;
            for (int i = m; i <= n; i++) {
                if (i == n) {
                   tailNode.next = curr.next; 
                }
                ListNode nextNode = curr.next;    
                curr.next = prevNode.next;
                prevNode.next = curr;
                curr = nextNode;
            }
            return dummy.next;
        }
    }

[PreviousReverse Linked List](/lintcode/linked_list/reverse-linked-list)
[NextRemove Linked List Elements](/lintcode/linked_list/remove-linked-list-elements)

Last updated 4 years ago

Was this helpful?

---

# Design Doubly Linked List | LintCode & LeetCode

Let's briefly review the structure definition of a node in the doubly linked list.

Copy

    // Definition for doubly-linked list.
    class DoublyListNode {
        int val;
        DoublyListNode next, prev;
        DoublyListNode(int x) {val = x;}
    }

Based on this definition, we are going to give you the solution step by step. The solution for the doubly linked list is similar to the one using singly linked list.

**1\. Initiate a new linked list: represent a linked list using the head node.**

Copy

    class MyLinkedList {
        private DoublyListNode head;
        /** Initialize your data structure here. */
        public MyLinkedList() {
            head = null;
        }
    }

**2\. Traverse the linked list to get element by index.**

Copy

    /** Helper function to return the index-th node in the linked list. */
    private DoublyListNode getNode(int index) {
        DoublyListNode cur = head;
        for (int i = 0; i < index && cur != null; ++i) {
            cur = cur.next;
        }
        return cur;
    }
    /** Helper function to return the last node in the linked list. */
    private DoublyListNode getTail() {
        DoublyListNode cur = head;
        while (cur != null && cur.next != null) {
            cur = cur.next;
        }
        return cur;
    }
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        DoublyListNode cur = getNode(index);
        return cur == null ? -1 : cur.val;
    }

**3\. Add a new node.**

Copy

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        DoublyListNode cur = new DoublyListNode(val);
        cur.next = head;
        if (head != null) {
            head.prev = cur;
        }
        head = cur;
        return;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        if (head == null) {
            addAtHead(val);
            return;
        }
        DoublyListNode prev = getTail();
        DoublyListNode cur = new DoublyListNode(val);
        prev.next = cur;
        cur.prev = prev;
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        if (index == 0) {
            addAtHead(val);
            return;
        }
        DoublyListNode prev = getNode(index - 1);
        if (prev == null) {
            return;
        }
        DoublyListNode cur = new DoublyListNode(val);
        DoublyListNode next = prev.next;
        cur.prev = prev;
        cur.next = next;
        prev.next = cur;
        if (next != null) {
            next.prev = cur;
        }
    }

Similar to the singly linked list, it takes `O(N)` time to get a node by index, where N is the length of the linked list. It is different from adding a new node after a given node.

**5\. Delete a node.**

Copy

    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        DoublyListNode cur = getNode(index);
        if (cur == null) {
            return;
        }
        DoublyListNode prev = cur.prev;
        DoublyListNode next = cur.next;
        if (prev != null) {
            prev.next = next;
        } else {
            // modify head when deleting the first node.
            head = next;
        }
        if (next != null) {
            next.prev = prev;
        }
    }

Similar to the add operation, it takes `O(N)` time to get the node by the index which is different from deleting a given node. However, it is different to the singly linked list. When we get the node we want to delete, we don't need to traverse to get its previous node but using the "prev" field instead.

[PreviousDesign Singly Linked List](/lintcode/linked_list/design-linked-list/design-singly-linked-list)
[NextPalindrome Linked List](/lintcode/linked_list/palindrome-linked-list)

Last updated 4 years ago

Was this helpful?

---