首页 > 代码库 > leetcode 链表题总结

leetcode 链表题总结

按照frequency来排序,总共27题

1、2. Add Two Numbers  https://leetcode.com/problems/add-two-numbers/#/description

两个链表相加,注意就是进位问题。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int flag = 0;
        ListNode result = new ListNode(0);
        ListNode node = result;
        while (l1 != null || l2 != null){
            int val = flag;
            if (l1 != null){
                val += l1.val;
                l1 = l1.next;
            }
            if (l2 != null){
                val += l2.val;
                l2 = l2.next;
            }
            if (val > 9){
                val -= 10;
                flag = 1;
            } else {
                flag = 0;
            }
            node.next = new ListNode(val);
            node = node.next;
        }
        if (flag == 1){
            node.next = new ListNode(1);
        }
        return result.next;
    }
}

 

 

2、237. Delete Node in a Linked List  https://leetcode.com/problems/delete-node-in-a-linked-list/#/description

删除链表中的节点。只给需要删除的节点。很简单,两行代码就搞定了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

 

3、206. Reverse Linked List  https://leetcode.com/problems/reverse-linked-list/#/description

反转链表。

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

4、148. Sort List  https://leetcode.com/problems/sort-list/#/description

链表排序。要求nlogn的时间复杂度和常数的空间复杂度。那么应用归并排序。

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        
        return sortList(l1, l2);
        
    }
    public ListNode sortList(ListNode node1, ListNode node2){
        ListNode node = new ListNode(0);
        ListNode nn = node;
        while (node1 != null && node2 != null){
            if (node1.val < node2.val){
                nn.next = node1;
                node1 = node1.next;
            } else {
                nn.next = node2;
                node2 = node2.next;
            }
            nn = nn.next;
        }
        while (node1 != null){
            nn.next = node1;
            nn = nn.next;
            node1 = node1.next;
        }
        while (node2 != null){
            nn.next = node2;
            nn = nn.next;
            node2 = node2.next;
        }
        return node.next;
    }
}

5、141. Linked List Cycle    https://leetcode.com/problems/linked-list-cycle/#/description

判断链表是否有环。

一个快,一个慢,判断是否会走到一起(如果成环一定可以走到一起)。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null){
            return false;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while (fast != null && fast.next != null && slow != fast){
            fast = fast.next.next;
            slow = slow.next;
        }
        return (fast == null || fast.next == null) ? false : true;
    }
}

 

6、328. Odd Even Linked List    https://leetcode.com/problems/odd-even-linked-list/#/description

将链表分为偶数和奇数两块,奇数放在前面,偶数放在后面。

刚开始看错题目,说的是将第偶数个放在一起,第奇数个放在一起,并非链表中的数值。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        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;
    }
}

 

 

7、21. Merge Two Sorted Lists  链表合并  https://leetcode.com/problems/merge-two-sorted-lists/#

 简单的两路归并。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0), node = head;;
        while (l1 != null && l2 != null){
            if (l1.val > l2.val){
                node.next = l2;
                l2 = l2.next;
            } else {
                node.next = l1;
                l1 = l1.next;
            }
            node = node.next;
        }
        if (l1 != null){
            node.next = l1;
        } else if (l2 != null){
            node.next = l2;
        }
        return head.next;
    }
}

 

8、160. Intersection of Two Linked Lists返回两个链表的第一个交点。  https://leetcode.com/problems/intersection-of-two-linked-lists/#/description

a、找出长度差,然后长的链表先行长度差个,然后依次比较,找出交点(没有就是null)。

b、用hash

/**
 * 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) {
        int len1 = 0, len2 = 0;
        ListNode node = headA;
        while (node != null){
            node = node.next;
            len1++;
        }
        node = headB;
        while (node != null){
            node = node.next;
            len2++;
        }
        if (len1 > len2){
            for (int i = 0; i < len1 - len2; i++){
                headA = headA.next;
            }
        } else {
            for (int i = 0; i < len2 - len1; i++){
                headB = headB.next;
            }
        }
        while (headA != headB){
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
}

另外,可以这样解。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //boundary check
    if(headA == null || headB == null) return null;
    
    ListNode a = headA;
    ListNode b = headB;
    
    //if a & b have different len, then we will stop the loop after second iteration
    while( a != b){
        //for the end of first iteration, we just reset the pointer to the head of another linkedlist
        a = a == null? headB : a.next;
        b = b == null? headA : b.next;    
    }
    
    return a;
}

 

 

 

9、138. Copy List with Random Pointer 拷贝随机链表  https://leetcode.com/problems/copy-list-with-random-pointer/#/description

a、hash

b、在每一个链表后面添加一个链表。

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null){
            return null;
        }
        RandomListNode node = head, next;
        while (node != null){
            next = node.next;
            node.next = new RandomListNode(node.label);
            node.next.next = next;
            node = next;
        }
        node = head;
        while (node != null){
            if (node.random != null){
                node.next.random = node.random.next;
            }
            node = node.next.next;
        }
        RandomListNode newHead = new RandomListNode(0), result = newHead;
        node = head;
        while (node != null){
            next = node.next.next;
            newHead.next = node.next;
            newHead = newHead.next;
            node.next = next;
            node = node.next;
        }
        return result.next;
    }
}

 

 

10、23. Merge k Sorted Lists  k个链表的合并。    https://leetcode.com/problems/merge-k-sorted-lists/#/description

k路归并,利用优先级队列PriorityQueue

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(0), node = head;
        int size = lists.length;
        if (size == 0){
            return null;
        }
        Comparator<ListNode> comparator = new Comparator<ListNode>(){
          public int compare(ListNode o1, ListNode o2){
              if (o1.val > o2.val){
                  return 1;
              } else if (o1.val < o2.val){
                  return -1;
              } else {
                  return 0;
              }
          }  
        };
        PriorityQueue<ListNode> queue = new PriorityQueue(size, comparator);
        for (int i = 0; i < size; i++){
            if (lists[i] != null)
                queue.add(lists[i]);
        }
        while (!queue.isEmpty()){
            node.next = queue.poll();
            node = node.next;
            if (node.next != null){
                queue.add(node.next);
            }
        }
        return head.next;
    }
}

 

 

11、234. Palindrome Linked List  判断是否是回文链表  https://leetcode.com/problems/palindrome-linked-list/#/solutions

(123,123)是回文,(123,321)不是。  

由于没有时间了,写上思路:a、利用栈,时间O(n),空间O(N);

             b、找到中点(fast、slow一快一慢来判断),后半部分反转。然后判断。

 

 

12、147. Insertion Sort List  链表插入排序  https://leetcode.com/problems/insertion-sort-list/#/description

没什么技巧和难点。

 

13、142. Linked List Cycle II  找出链表循环的起点  https://leetcode.com/problems/linked-list-cycle-ii/#/description

与第五题也就是141相同,相遇的点就是循环的起点(数学方法证明)。

 

14、19. Remove Nth Node From End of List  删除倒数第n个节点    https://leetcode.com/problems/remove-nth-node-from-end-of-list/#/description

fast先走n个节点,然后slow再走,直到 fast == null为止,跳过slow.next即可。

这里需要了解n的范围,会不会超过长度,如果超过了长度要怎么办。

 

15、143. Reorder List  将链表按照固定方式改写。    https://leetcode.com/problems/reorder-list/#/description

Given a singly linked list LL0→L1→…→Ln-1→Ln,
reorder it to: L0→LnL1→Ln-1→L2→Ln-2→…

1、用list或者数组记录

2、用双向队列(Deque)

3、链表分成两半,然后后一半反转,然后合并两个链表。

 

 

 

16、24. Swap Nodes in Pairs  节点两两交换    https://leetcode.com/problems/swap-nodes-in-pairs/#/description

a、递归实现

b、非递归

 

 

17、203. Remove Linked List Elements  删除某个值    https://leetcode.com/problems/remove-linked-list-elements/#/description

遍历直接删除就行了

 

 

18、83. Remove Duplicates from Sorted List  删除重复的数    https://leetcode.com/problems/remove-duplicates-from-sorted-list/#/description

也是递归、非递归实现。

 

19、109. Convert Sorted List to Binary Search Tree  排序好的链表建树    https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/#/description

递归实现,二分查找。

 

20、92. Reverse Linked List II   链表的部分反转    https://leetcode.com/problems/reverse-linked-list-ii/#/description

 

 

21、86. Partition List   划分链表的值    https://leetcode.com/problems/partition-list/#/description

给定一个值,把小于x的值放在左边,大于等于x的值放在右边,保持相对顺序。

没什么难点。

 

 

22、25. Reverse Nodes in k-Group    部分反转    https://leetcode.com/problems/reverse-nodes-in-k-group/#/description

也是递归和非递归的实现。

 

 

 

23、61. Rotate List    旋转链表    https://leetcode.com/problems/rotate-list/#/description

从倒数第k个位置开始旋转一下链表。

需要判断k是否大于len。

 

 

24、82. Remove Duplicates from Sorted List II    去掉重复的数字(一个都不留)    https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/#/description

没什么难点。遍历一次就行了

 

25、445. Add Two Numbers II    链表相加(与之前一体的区别是反过来了,而且不允许反转链表)

1、首先想到的应该是反转链表,然后求出答案,这样空间复杂度是O(n);

2、借助辅助空间,stack。

3、日常递归实现。 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> l1_stack = new Stack();
        Stack<Integer> l2_stack = new Stack();
        while (l1 != null){
            l1_stack.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null){
            l2_stack.add(l2.val);
            l2 = l2.next;
        }
        ListNode head = new ListNode(0), curr = null;
        int flag = 0;
        while (!l1_stack.isEmpty() || !l2_stack.isEmpty() || flag == 1){
            int num = flag;
            if (!l1_stack.isEmpty()){
                num += l1_stack.pop();
            }
            if (!l2_stack.isEmpty()){
                num += l2_stack.pop();
            }
            if (num > 9){
                num -= 10;
                flag = 1;
            } else {
                flag = 0;
            }
            ListNode node = new ListNode(num);
            node.next = curr;
            curr = node;
            head.next = node;
        }
        return head.next;
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 = getLen(l1);
        int len2 = getLen(l2);
        ListNode head = new ListNode(1);
        head.next = len1 > len2 ? helper(l1, l2, len1 - len2) : helper(l2, l1, len2 - len1);
        if (head.next.val > 9){
            head.next.val -= 10;
            return head;
        }
        return head.next;
    }
    
    public ListNode helper(ListNode l1, ListNode l2, int offset){
        if (l1 == null){
            return null;
        }
        ListNode node = offset == 0 ? new ListNode(l1.val + l2.val) : new ListNode(l1.val);
        ListNode next = offset == 0 ? helper(l1.next, l2.next, 0) : helper(l1.next, l2, offset - 1);
        
        if (next != null && next.val > 9){
            next.val -= 10;
            node.val += 1;
        }
        node.next = next;
        
        return node;
    }
    
    public int getLen(ListNode node){
        int len = 0;
        while (node != null){
            node = node.next;
            len++;
        }
        return len;
    }
}

 

 

26、379. Design Phone Directory  设计电话字典。设计题。并不知道哪里用到了链表。    https://leetcode.com/problems/design-phone-directory/#/description

 a、直接用数组就可以实现。

b、用队列 + set可以实现(更快一些,数组每次get需要遍历)。

这里用了数组实现。

public class PhoneDirectory {

    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    private int[] phone;
    public PhoneDirectory(int maxNumbers) {
        phone = new int[maxNumbers];
        for (int i = 0; i < maxNumbers; i++){
            phone[i] = 1;
        }
    }
    
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    public int get() {
        for (int i = 0; i < phone.length; i++){
            if (phone[i] == 1){
                phone[i] = 0;
                return i;
            }
        }
        return -1;
    }
    
    /** Check if a number is available or not. */
    public boolean check(int number) {
        if (number < 0 || number > phone.length){
            return false;
        }
        return phone[number] == 1;
    }
    
    /** Recycle or release a number. */
    public void release(int number) {
        phone[number] = 1;
    }
}

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj.get();
 * boolean param_2 = obj.check(number);
 * obj.release(number);
 */

 

 

 

27、369. Plus One Linked List  链表+1    https://leetcode.com/problems/plus-one-linked-list/#/description

 1、递归。、

2、判断末尾有多少个连续的9即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode plusOne(ListNode head) {
        ListNode node = new ListNode(1);
        node.next = head;
        plusOneHelper(head);
        if (node.next.val > 9){
            node.next.val -= 10;
            return node;
        }
        return node.next;
    }
    
    public void plusOneHelper(ListNode node){
        if (node.next == null){
            node.val += 1;
            return ;
        } else {
            plusOneHelper(node.next);
            if (node.next.val > 9){
                node.next.val -= 10;
                node.val += 1;
            }
        }
        return ;
    }
    
}

 

leetcode 链表题总结