[关闭]
@Yano 2015-12-30T03:23:34.000000Z 字数 11605 阅读 11237

LeetCode之Linked List题目汇总

LeetCode

我的博客:http://blog.csdn.net/yano_nankai
LeetCode题解:https://github.com/LjyYano/LeetCode


LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总


文章目录:


Add Two Numbers

You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8


    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        if (l1 == null && l2 == null) {
            return null;
        }

        if (l1 == null) {
            return l2;
        }

        if (l2 == null) {
            return l1;
        }

        ListNode p1 = l1;
        ListNode p2 = l2;

        int carry = 0;

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

        while (carry != 0 || p1 != null || p2 != null) {

            int v1 = 0;
            if (p1 != null) {
                v1 = p1.val;
                p1 = p1.next;
            }

            int v2 = 0;
            if (p2 != null) {
                v2 = p2.val;
                p2 = p2.next;
            }

            int tmp = v1 + v2 + carry;
            carry = tmp / 10;
            head.next = new ListNode(tmp % 10);
            head = head.next;
        }

        return result.next;
    }

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.


参考:LeetCode 108 Convert Sorted Array to Binary Search Tree

但是不能将linked list转换成arraylist,会超时。思路:快慢指针。

    ListNode cutAtMid(ListNode head) {

        if (head == null) {
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;
        ListNode pslow = head;

        while (fast != null && fast.next != null) {
            pslow = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        pslow.next = null;
        return slow;
    }

    public TreeNode sortedListToBST(ListNode head) {

        if (head == null) {
            return null;
        }

        if (head.next == null) {
            return new TreeNode(head.val);
        }

        ListNode mid = cutAtMid(head);

        TreeNode root = new TreeNode(mid.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);

        return root;
    }

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.


题目是让删除链表中的指定结点,这个结点不是尾结点。

要求时间复杂度是O(1)

我们通常的想法是:要删除链表的一个结点node,必须找到node的前驱结点pre,使用pre.next = node.next才能删除。但是单链表不遍历的话,是无法找到pre的,所以时间复杂度是O(n)。

要删除node,我们为什么不利用后继结点succ呢?

我们可以把succ的值复制到node中,然后删除succ!

    public void deleteNode(ListNode node) {

        if (node == null) {
            return;
        }

        node.val = node.next.val;
        node.next = node.next.next;
    }

Insertion Sort List

Sort a linked list using insertion sort.


    public ListNode insertionSortList(ListNode head) {

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

        final ListNode _head = new ListNode(Integer.MIN_VALUE);
        _head.next = head;

        head = head.next;
        _head.next.next = null;

        next: while (head != null) {

            ListNode taken = head;
            head = head.next;

            ListNode cur = _head.next;
            ListNode last = _head;

            while (cur != null) {

                if (cur.val > taken.val) {
                    // insert
                    last.next = taken;
                    taken.next = cur;

                    continue next;

                }

                cur = cur.next;
                last = last.next;
            }

            last.next = taken;
            taken.next = null;

        }

        return _head.next;

    }

Intersection of Two Linked Lists

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

For example, the following two linked lists:

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

begin to intersect at node c1.

Notes:

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.


  1. 记链表A的长度是lenA,最后一个结点为p;链表B的长度是lenB,最后一个结点为q。

  2. 如果p≠q,则链表A、B不相交,直接返回null。因为如果链表A、B在某处相交,那么后面的结点完全相同(如题目中所示,是Y型的)。

  3. 如果p=q,则链表A、B在某处相交。让长的链表走|lenA−lenB|步(按照末端对齐),然后两个链表同时向前走,相等结点即为相交公共结点。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        if (headA == null || headB == null) {
            return null;
        }
    
        // 计算链表A的长度
        int lenA = 1;
        ListNode p = headA;
        while (p.next != null) {
            lenA++;
            p = p.next;
        }
    
        // 计算链表B的长度
        int lenB = 1;
        ListNode q = headB;
        while (q.next != null) {
            lenB++;
            q = q.next;
        }
    
        // 若A和B的最后一个结点不等,则不相交,返回null
        if (p != q) {
            return null;
        }
    
        // 链表按照尾部对齐
        if (lenA > lenB) {
            int t = lenA - lenB;
            while (t-- != 0) {
                headA = headA.next;
            }
        } else {
            int t = lenB - lenA;
            while (t-- != 0) {
                headB = headB.next;
            }
        }
    
        // 同时向前走
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
    
        return headA;
    }
    

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?


快慢指针,定义两个指针,一个每次走一步,另一个每次走两步。如果快指针“遇到”了慢指针,说明有环。

    public boolean hasCycle(ListNode head) {

        if (head == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null) {

            if (fast.next == null || fast.next.next == null) {
                return false;
            }

            if (slow == fast) {
                return true;
            }

            fast = fast.next.next;
            slow = slow.next;
        }

        return false;
    }

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?


以下参考:[原]求单链表环的入口结点 Linked List Cycle II

slow指针每次走1步,fast指针每次走2步。如果链表有环,那么两个指针一定会相遇。

设链表头到环入口结点的结点数目是a,环内的结点数目r。假设相遇时,fast指针已经绕环转了n圈,比slow多走了n*r步。假设环的入口结点到相遇结点的结点数目为x。

那么在相遇时,slow走了a+x步,fast走了a+x+n*r步。

由于fast的步调是slow的两倍,所以有a+x = n*r。因而,a = n*r - x

显然,从相遇位置开始,走n*r - x步,一定可以到达环的入口结点;从链表头开始,走a步,也会到达环的入口。并且我们得到了a = n*r - x。所以我们让两个指针,一个从相遇位置出发一个从链表头出发,让他们都单步前进。因为a = n*r - x,所以他们一定会在环的入口相遇。

    public ListNode detectCycle(ListNode head) {

        if (head == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        boolean meet = false;
        int len = 0;

        // 判断是否有环,并计数
        while (fast != null) {

            if (fast.next == null || fast.next.next == null) {
                return null;
            }

            if (slow == fast) {
                if (meet) {
                    break;
                }
                meet = true;
            }

            fast = fast.next.next;
            slow = slow.next;

            if (meet) {
                len++;
            }
        }

        if (meet) {

            slow = head;
            fast = head;

            // fast先走len步
            for (int i = 0; i < len; i++) {
                fast = fast.next;
            }

            // slow从起始点出发,fast从len处出发
            // 二者相遇的结点,即为入环结点
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }

            return slow;
        }

        return null;
    }

Merge Two Sorted Lists

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.


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        if (l1 == null && l2 == null) {
            return null;
        }

        if (l1 == null) {
            return l2;
        }

        if (l2 == null) {
            return l1;
        }

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

        while (l1 != null && l2 != null) {

            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }

            p = p.next;
        }

        if (l1 != null) {
            p.next = l1;
        } else {
            p.next = l2;
        }

        return head.next;
    }

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?


O(n) time and O(1) space的解法:

  1. 找到链表中点
  2. 将后半段链表翻转
  3. 对比两段链表

说明:不用管链表是奇数还是偶数,如果链表长度是偶数,那么翻转后,前段和后段链表长度相等;如果是奇数,后段链表长1个结点,所以只需要判断前段结点是否遍历结束。

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

        // 翻转后段链表
        ListNode tail = reverseList(slow);

        while (head != slow) {
            if (head.val != tail.val) {
                return false;
            }
            head = head.next;
            tail = tail.next;
        }

        return true;
    }

    public ListNode reverseList(ListNode head) {

        if (head == null) {
            return null;
        }

        if (head.next == null) {
            return head;
        }

        ListNode tail = head.next;
        ListNode reversed = reverseList(head.next);

        // 前后翻转tail和head
        tail.next = head;
        head.next = null;

        return reversed;

    }

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.


    public ListNode deleteDuplicates(ListNode head) {

        if (head == null) {
            return null;
        }

        if (head.next == null) {
            return head;
        }

        ListNode node = head;

        while (node.next != null) {

            // 如果元素不重复,跳过
            if (node.val != node.next.val) {
                node = node.next;
            } else {
                // 重复,则跳过下一个
                while (node.next != null && node.val == node.next.val) {
                    node.next = node.next.next;
                }
            }
        }

        return head;
    }

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.


    public ListNode deleteDuplicates(ListNode head) {

        if (head == null) {
            return null;
        }

        if (head.next == null) {
            return head;
        }

        int val = head.val;

        ListNode node = head;

        boolean killme = false;

        while (node.next != null && node.next.val == val) {
            node = node.next;
            killme = true;
        }

        if (killme) {
            head = deleteDuplicates(node.next);
        } else {
            head.next = deleteDuplicates(node.next);
        }

        return head;
    }

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

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.
Try to do this in one pass.


题目中说n是合法的,就不用对n进行检查了。用标尺的思想,两个指针相距为n-1,后一个到表尾,则前一个到n了。(p为second,q为first)

  1. 指针p、q指向链表头部; 
  2. 移动q,使p和q差n-1; 
  3. 同时移动p和q,使q到表尾; 
  4. 删除p。

    public ListNode removeNthFromEnd(ListNode head, int n) {
    
        if (head == null || head.next == null) {
            return null;
        }
    
        ListNode first = head;
        ListNode second = head;
    
        for (int i = 0; i < n; i++) {
            first = first.next;
            if (first == null) {
                return head.next;
            }
        }
    
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
    
        second.next = second.next.next;
    
        return head;
    }
    

Reverse Linked List

Reverse a singly linked list.

click to show more hints.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?


    public ListNode reverseList(ListNode head) {

        if (head == null) {
            return null;
        }

        if (head.next == null) {
            return head;
        }

        ListNode tail = head.next;
        ListNode reversed = reverseList(head.next);

        // 前后翻转tail和head
        tail.next = head;
        head.next = null;

        return reversed;
    }

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULLm = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.


    public ListNode reverseBetween(ListNode head, int m, int n) {

        if (head == null || head.next == null || m == n) {
            return head;
        }

        ListNode fakeHead = new ListNode(-1);
        fakeHead.next = head;

        // 先向后移m步
        ListNode pre = fakeHead;
        for (int i = 1; i < m; i++) {
            pre = pre.next;
        }

        // 对后面的n-m个结点,逆置
        ListNode mNode = pre.next;
        for (int i = m; i < n; i++) {
            ListNode cur = mNode.next;
            mNode.next = cur.next;
            cur.next = pre.next;
            pre.next = cur;
        }

        return fakeHead.next;
    }

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.


    public ListNode rotateRight(ListNode head, int k) {

        if (head == null)
            return null;

        int len = 1;

        ListNode tail = head;

        while (tail.next != null) {
            len++;
            tail = tail.next;
        }

        tail.next = head; // cycle

        k %= len;

        for (int i = 1; i < len - k; i++) {
            head = head.next;
        }

        try {
            return head.next;
        } finally {
            head.next = null; // cut
        }
    }

Sort List

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


O(n log n) 的时间复杂度,归并排序最好,因为它不会因为输入序列的基本有序而变化。

参考:LeetCode 021 Merge Two Sorted Lists

  1. 首先将List分成两个
  2. MergeSort(left) ,MegerSort(right)
  3. LeetCode 021 Merge Two Sorted Lists

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
        ListNode rt = new ListNode(0);
        ListNode h = rt;
    
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                rt.next = l1;
                l1 = l1.next;
            } else {
                rt.next = l2;
                l2 = l2.next;
            }
    
            rt = rt.next;
        }
    
        if (l1 != null)
            rt.next = l1;
        else
            rt.next = l2;
    
        return h.next;
    
    }
    
    public ListNode sortList(ListNode head) {
        if (head == null)
            return null;
        if (head.next == null)
            return head;
    
        ListNode fast = head.next;
        ListNode slow = head;
    
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
    
        ListNode h2 = slow.next;
        slow.next = null;
    
        return mergeTwoLists(sortList(head), sortList(h2));
    
    }
    

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.


    public ListNode swapPairs(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode fakeHead = new ListNode(0);
        fakeHead.next = head;

        ListNode p1 = fakeHead;
        ListNode p2 = head;

        while (p2 != null && p2.next != null) {
            ListNode nextStart = p2.next.next;
            p2.next.next = p2;
            p1.next = p2.next;
            p2.next = nextStart;
            p1 = p2;
            p2 = p2.next;
        }

        return fakeHead.next;
    }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注