Tag: Linked List

Posted 2022-07-22Updated 2022-07-22LeetCode / Medium3 minutes read (About 442 words)

Question

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Solution 1

生成前后两个部分的dummy链表头。
遍历原链表，当当前值小于x时则将当前节点添加到第一个链表头后。
当当前值大于x时则将当前节点添加到第二个链表头后。

遍历完成后将第二个链表头的下一个节点添加到第一个链表的下一个节点上。然后将第二个链表的尾部指向null。

返回第一个dummy链表节点的下一个节点即可。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(), dummy2 = new ListNode();
        ListNode hd1 = dummy1, hd2 = dummy2;
        while(head != null){
            if(head.val < x){
                dummy1.next = head;
                dummy1 = dummy1.next;
            }
            else{
                dummy2.next = head;
                dummy2 = dummy2.next;
            }
            head = head.next;
        }
        dummy1.next = hd2.next;
        dummy2.next = null;
        
        return hd1.next;
    }
}

Solution 2

遍历整个链表，根据各个节点的值将其保存在两个队列中。

设置一个dummy节点头，将两个队列中的节点按顺序挤出并生成新链表。
返回dummy节点头的下一个节点即可。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        Queue<ListNode> q1 = new LinkedList<>();
        Queue<ListNode> q2 = new LinkedList<>();
        while(head != null){
            if(head.val < x) q1.add(head);
            else q2.add(head);
            head = head.next;
        }
        
        ListNode dummy = new ListNode();
        ListNode res = dummy;
        
        while(!q1.isEmpty()){
            res.next = q1.poll();
            res = res.next;
        }
        
        while(!q2.isEmpty()){
            res.next = q2.poll();
            res = res.next;
        }
        res.next = null;
        return dummy.next;
    }
}

Posted 2022-05-06Updated 2022-05-05LeetCode / Easy / 复习2 minutes read (About 353 words)

202. Happy Number

Question

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.

Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.

Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Solution

首先证明，快乐数的计算不会趋近于无穷大。
我们可以考虑每一个位数的最大数字（9999…999）。
其下一个数值等于(81*n)。
对于三位数以下，其最大的值得下一个结果不会大于243。
对于四位数以上，下一个结果会快速收缩到三位数。
因此计算结果不会趋近于无穷。

当我们计算快乐数的值时，形成了一个隐式链表。
因此我们可以用快慢指针的方式，查询链表上是否有环。
快指针比慢指针初始值快1个单位，且移动速度为慢指针的一倍。
如果链表中有环，则两者终能相遇。
如果fast指针先走到1，等于走到了链表的终点。

Code

class Solution {
    public boolean isHappy(int n) {
        int slow = n, fast = getNext(n);
        while(fast != 1 && fast != slow){
            fast = getNext(getNext(fast));
            slow = getNext(slow);
        }
        return fast == 1;
    }
    
    private int getNext(int n){
        int sum = 0;
        while(n != 0){
            int digit = n % 10;
            sum += (digit * digit);
            n = n / 10;
        }
        return sum;
    }
}

Posted 2022-04-27Updated 2022-04-27LeetCode / Medium / 复习3 minutes read (About 484 words)

707. Design Linked List

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

MyLinkedList() Initializes the MyLinkedList object.

int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.

void addAtHead(int val) 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.

void addAtTail(int val) Append a node of value val as the last element of the linked list.

void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.

void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

单链表，设置一个哨兵节点在头部。
设置辅助方法，取得index的前一个节点。
addAtHead和addAtTail都可以采用addAtIndex实现。

采用双链表速度可以更快。

class MyLinkedList {
    ListNode head;
    int size;
    public MyLinkedList() {
        ListNode dummy = new ListNode(0);
        head = dummy;
        size = 0;
    }
    
    public ListNode getPrev(int index){
        ListNode prev = head;
        for(int i = 0; i < index; i++){
            prev = prev.next;
        }
        return prev;
    }
    
    public int get(int index) {
        if(index >= size) return -1;
        return getPrev(index).next.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index > size) return;
        ListNode prev = getPrev(index);
        ListNode temp = prev.next;
        prev.next = new ListNode(val);
        prev.next.next = temp;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index >= size) return;
        if(index == size-1){
            ListNode prev = getPrev(index);
            prev.next = null;
            size--;
            return;
        }
        ListNode prev = getPrev(index);
        prev.next = prev.next.next;
        size--;
    }
    
    private void print(){
        ListNode root = head.next;
        while(root != null){
            System.out.print(root.val+" ->   ");
            root = root.next;
        }
        System.out.println("Size:   "+size);
    }
    
    class ListNode{     
        int val;
        ListNode next;
        public ListNode(int v){
            val = v;
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

Posted 2022-04-26Updated 2022-04-26LeetCode / Medium / 复习2 minutes read (About 267 words)

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

先建立一个哨兵节点，next指向head。
交换时同时传入前一个节点pre和当前节点root。
当当前节点非null且下一个节点非null，则可以交换两个节点。
首先保存当前节点的下一个节点next和下一个节点的下一个节点last。

1.将pre指向next。
2.将next指向root。
3.将root指向last。
4.处理下一组节点，root作为pre，root.next作为root递归。
最后返回哨兵节点的next。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        swap(dummy, head);
        return dummy.next;
    }
    
    private void swap(ListNode pre, ListNode root){
        if(root == null || root.next == null){
            return;
        }
        else if(root != null && root.next != null){
            
            ListNode last = root.next.next;
            ListNode next = root.next;
            pre.next = next;
            next.next = root;
            root.next = last;
        }
        swap(root, root.next);
    }
}

Posted 2022-04-26Updated 2022-04-26LeetCode / Easy2 minutes read (About 353 words)

160. Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

计算两个链表的长度。将长的链表向下移动两者长度的差，对齐两个链表的长度。
同时向下移动两个链表，如果两个节点的内存地址相同，则返回节点。否则返回null。

/**
 * 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 sizeA = 0, sizeB = 0;
        ListNode l1 = headA, l2 = headB;
            
        while(l1 != null){
            l1 = l1.next;
            sizeA++;
        }
        while(l2 != null){
            l2 = l2.next;
            sizeB++;
        }
        if(sizeA > sizeB){
            int size = sizeA - sizeB;
            while(size != 0){
                headA = headA.next;
                size--;
            }
        }
        else{
            int size = sizeB - sizeA;
            while(size != 0){
                headB = headB.next;
                size--;
            }
        }
        while(headA != null){
            if(headA == headB) return headA;
                headA = headA.next;
                headB = headB.next;
        }
        return null;
    }
}

遍历移动一个链表，将其加入哈希集合。
然后移动另一个链表，如果哈希集合中有重复节点，则返回该节点。

/**
 * 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) {
        HashSet<ListNode> set = new HashSet<>();
        while(headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null){
            if(set.contains(headB)) return headB;
            headB = headB.next;
        }
        return null;
    }
}

Posted 2022-04-25Updated 2022-04-25LeetCode / Medium / 复习3 minutes read (About 411 words)

142. Linked List Cycle II

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

快慢指针。快指针的移动速度是慢指针的两倍。
设环外长度为a，b是快指针和慢指针相遇的位置，c是环中剩余位置。
可以由此得到公式a + (n + 1)b + nc = 2(a + b)，也就是a = c + (n - 1)(b + c)
由于（b + c）是环的长度。因此，当两个指针相遇时，在头部设置一个新节点。慢指针和新指针将在循环入口处相遇，此时返回节点。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if( head == null || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow.equals(fast)) break;
        }
        
        if(fast == null || fast.next == null){
            return null;
        }
        
        ListNode root = head;
        while(!root.equals(slow)){
            slow = slow.next;
            root = root.next;
        }
        return root;
    }
}

哈希表，递归并将节点加入哈希集合，如果重复则返回节点，反之返回null。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    HashSet<ListNode> set;
    public ListNode detectCycle(ListNode head) {
        set = new HashSet<>();
        return findCycle(head, 0);
    }
    
    private ListNode findCycle(ListNode root, int count){
        if(root == null){
            return null;
        }
        if(set.contains(root)){
            return root;
        }
        set.add(root);
        count++;
        return findCycle(root.next, count);
    }
}

Posted 2022-04-25Updated 2022-04-25LeetCode / Medium2 minutes read (About 348 words)

2. Add Two Numbers

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 contains a single digit. Add the two numbers and return the sum as a linked list.

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

递归，每次递归时建立root的next节点，然后将root移动到root.next。
计算两个节点的和并填入root节点。每次计算时需要计算是否进位。
递归两个节点的next节点，并将carry传入。
当一个节点为null时，只递归和计算另一个节点。
当两个节点为null时，如果有carry需要将其放入新节点，如果没有则返回。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode();
        addTwo(l1,l2,root,0);
        return root.next;
    }
    
    private void addTwo(ListNode l1, ListNode l2, ListNode root, int carry){
        if(l1 == null && l2 == null && carry == 0){
            return;
        }
        else if(l1 == null && l2 == null){
            root.next = new ListNode();
            root = root.next;
            root.val = carry;
            return;
        }
        else if(l1 == null){
            root.next = new ListNode();
            root = root.next;
            root.val = (l2.val + carry) % 10;
            carry = (l2.val + carry) / 10;
            addTwo(null, l2.next, root, carry);
            return;
        }
        else if(l2 == null){
            root.next = new ListNode();
            root = root.next;
            root.val = (l1.val + carry) % 10;
            carry = (l1.val + carry) / 10;
            addTwo(null, l1.next, root, carry);
            return;
        }
        root.next = new ListNode();
        root = root.next;
        root.val = (l1.val + l2.val + carry) % 10;
        carry = (l1.val + l2.val + carry) / 10;

        addTwo(l1.next, l2.next, root, carry);
    }
}

Posted 2022-04-18Updated 2022-04-17LeetCode / Medium / 复习2 minutes read (About 228 words)

82. Remove Duplicates from Sorted List II

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

使用队列暂存遍历的节点。
初始化prev为一个dummy节点。
如果当前节点不等于队列里节点的值，则倾倒出队列里的值。如果队列此时只有一个值，则将其添加到prev.next。
遍历完毕后如果队列内只有一个值则将其设置到prev.next。
最后返回dummy.next。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        Queue<ListNode> q = new LinkedList();
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        ListNode curr = head; 
        while(curr != null){
            if(q.isEmpty() || curr.val == q.peek().val){
                q.offer(curr);
                curr = curr.next;
            }
            else{
                if(q.size()==1){
                    prev.next = q.poll();
                    prev = prev.next;
                    prev.next = null;
                }
                else{
                    q.clear();   
                }
            }
        }
        
        if(q.size()==1){
            prev.next = q.poll();
        }
        
        return dummy.next;
    }

}

Posted 2022-04-10Updated 2022-04-09LeetCode / Easya minute read (About 167 words)

83. Remove Duplicates from Sorted List

问题
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

设置前一个节点和当前节点两个指针。
由于是有数的链表，遍历时可以直接比较两个节点。
如相等则前一个节点的next指向当前节点的next。

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

Posted 2022-04-10Updated 2022-04-09LeetCode / Easy / 复习2 minutes read (About 268 words)

206. Reverse Linked List

问题
Given the head of a singly linked list, reverse the list, and return the reversed list.

翻转列表，当链表长度不足时，直接返回原链表。
将头元素设置到preNode，同时将其next设置为null，作为新链表的尾。
将其余的元素设置到curNode。

当当前节点不为null时
遍历：

将curNode的next保存在temp。
将curNode的next指向preNode，作为preNode的上一个节点。
将preNode指向curNode，完成交换。
将curNode指向temp，curNode变为原来的curNode的next。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
        if( head == null ){   //if not enough, return head
            return head;
        }
        if ( head.next == null ){
            return head;
        }
        
        ListNode preNode = head;    //set head to preNode, it will be the last node in the end
        ListNode curNode = head.next;   //curNode move to next
        preNode.next = null;    //only preserve one head node
        ListNode temp;
        
        while( curNode != null ){
            temp = curNode.next;    //preserve nodes after curNode
            curNode.next = preNode; //cur -> pre
            preNode = curNode;  //set back reversed list to preNode
            curNode = temp; //put back preserved nodes, curNode move to the next
        }
        return preNode;
    }

}

Posted 2022-04-09Updated 2022-04-08LeetCode / Easya minute read (About 224 words)

203. Remove Linked List Elements

问题
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

设置哨兵节点，将其next指向头部。
设置前节点，将其指向哨兵节点。
设置尾部节点，并指向头部。
移动当前节点尾部，如尾部的val等于需要删去的val，则将前节点的next指向尾部的next。
尾部的next如为null，则前节点的next指向null。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null){
            return head;
        }
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        
        ListNode preNode = dummyHead;
        ListNode tail = dummyHead.next;
        
        while( tail != null ){
            if ( tail.next == null && tail.val == val ){
                preNode.next = null;
                break;
            }
            else if (tail.val == val){
                preNode.next = tail.next;
                tail = preNode.next;
            }
            else{
                preNode = preNode.next;
                tail = tail.next;
            }
        }
        
        return dummyHead.next;
    }
}

Posted 2022-04-09Updated 2022-04-20LeetCode / Easy / 复习a minute read (About 217 words)

21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

先设置空的哨兵节点，然后将尾部指针指向这个节点。
遍历两个链表，将尾部节点的下一个值指向两个节点中值较小的一个。
然后将指针移动到下一个值。
最后返回哨兵节点的下一个节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;

        
        while ( list1 != null && list2 !=null ){
            if (list1.val < list2.val){
                tail.next = list1;
                list1 = list1.next;
                tail = tail.next;
            }
            else{
                tail.next = list2;
                list2 = list2.next;
                tail = tail.next;
            }
 
        }
        
        if ( list1 == null){
            tail.next = list2;
        }
        else {
            tail.next = list1;
        }
        
        return dummyHead.next;
    }
}

Posted 2022-04-07Updated 2022-04-20LeetCode / Mediuma minute read (About 166 words)

19. Remove Nth Node From End of List

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

双指针，同时记录前n个节点和当前节点。
当前指针到链表尾部时，删除前面的指针，注意处理edge cases。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode preNode = null;
        ListNode removedNode = head;
        ListNode fastNode = head;
        for ( int i = 0; i < n; i++ ){
            fastNode = fastNode.next;
        }
        
        while ( fastNode != null ){
            fastNode = fastNode.next;
            preNode = removedNode;
            removedNode = removedNode.next;
        }
        
        if ( removedNode == head ){
            head = head.next;
        }
        else if ( removedNode.next == null){
            preNode.next = null;
        }
        else{
            preNode.next = removedNode.next;
        }
        
        return head;
    }
}

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Recents

Archives

Links