春招冲刺百题计划|链表

Java基础复习

1. Java数组的声明与初始化
2. Java ArrayList
3. Java HashMap
4. Java String 类
5. Java LinkedList
6. Java Deque继承LinkedList
7. Java Set
8. Java 队列
9. 优先队列！！！
10. Java数组划分
11. Java数组转ArrayList
12. String 转数字
13. String

第一题：2. 两数相加

还是比较简单的一题

/**
 * 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) {
        int k=0;
        ListNode tmp = new ListNode();
        ListNode res = tmp;
        int last = 0;
        while(l1!=null&&l2!=null){
            tmp.next = new ListNode((l1.val+l2.val + last)%10);
            last = (l1.val+l2.val+last)/10;
            tmp = tmp.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        while(l1!=null){
            tmp.next = new ListNode((l1.val+last)%10);
            last = (l1.val+last)/10;
            tmp = tmp.next;
            l1 = l1.next;
        }
        while(l2!=null){
            tmp.next = new ListNode((l2.val+last)%10);
            last = (l2.val+last)/10;
            tmp = tmp.next;
            l2 = l2.next;
        }
        while(last!=0){
            tmp.next = new ListNode(last%10);
            last = last/10;
            tmp = tmp.next;
        }
        return res.next;


    }
}

第二题：61. 旋转链表

首先就是很麻烦的想法。

/**
 * 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 rotateRight(ListNode head, int k) {
        if(head==null){
            return head;
        }
        //最简单，拿一个数组来存储val，然后
        List<Integer> list = new ArrayList<Integer>();
        ListNode newHead = new ListNode(head.val, head.next);
        while(newHead!=null){
            list.add(newHead.val);
            newHead = newHead.next;
        }
        k = k%list.size();
        List<Integer> list2 = new ArrayList<Integer>(list.size());
        for(int i=0; i<list.size(); i++){
           list2.add(list.get((i-k+list.size())%list.size()));
        }
        System.out.print(list2);
        ListNode tmp = new ListNode();
        ListNode res = tmp;
        for(int i=0; i<list.size(); i++){
           tmp.next = new ListNode(list2.get(i));
           tmp = tmp.next;
        }
        return res.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 rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        int add = n - k % n;//找到断点处
        if (add == n) {
            return head;
        }
        iter.next = head; //成环
        while (add-- > 0) {
            iter = iter.next;
        }
        ListNode ret = iter.next;//新起点
        iter.next = null; //断开
        return ret;
    }
}

第三题：82. 删除排序链表中的重复元素 II

原来刷代码随想录的时候，遇到这种题目，可以添加一个空的头指针，方便统一处理。

/**
 * 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) {
        while(head==null||head.next==null){
            return head;
        }
        ListNode newhead = new ListNode(-1, head);
        ListNode l = newhead, r=head.next;
        while(l!=null&&r!=null){
            if(l.next.val!=r.val){
                l=l.next;
                r=r.next;
            }else{
                while(r!=null&&r.val==l.next.val){
                    r = r.next;
                }
                l.next = r;
                if(r!=null)
                    r = r.next;
            }
            
        }
        return newhead.next;
    }
}

第四题：92. 反转链表 II

/**
 * 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 reverseBetween(ListNode head, int left, int right) {
        //原本想要尝试成环断开的方法，写完才发现，思路是错的。
        if(left==right){
            return head;
        }

        ListNode newHead = new ListNode(0, head);
        ListNode beforeLeft = newHead, afterRight = head;
        int i = 1;
        while(i<left){
            beforeLeft = beforeLeft.next;
            i++;
        }
        afterRight = beforeLeft;
        while(i<=right){
            afterRight = afterRight.next;
            i++;
        }
        ListNode l = beforeLeft.next, r = afterRight; //l和r是需要翻转的那一部分的头和尾。
        afterRight = afterRight.next; //无需翻转的后半部分
        i=1;
        while(l!=r){
            beforeLeft.next = r; // 1->4
            beforeLeft = beforeLeft.next; //1->4->?
            i++;
            r = l;//以下是找3的过程
            int j = 0;
            while(j<right-left+1-i){
                r = r.next;
                j++;
            }
        }
        beforeLeft.next = r; 
        beforeLeft = beforeLeft.next;
        beforeLeft.next = afterRight;
        return newHead.next;

    }
}

第五题：24. 两两交换链表中的节点

/**
 * 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) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode newhead = new ListNode(0, head);
        ListNode l = newhead, r=head.next;
        while(r!=null){
            System.out.println(r.val);
            l.next.next = r.next;
            r.next = l.next;
            l.next = r;
            l = l.next.next;
            if(l.next==null){
                break;  
            }
            r = l.next.next;
        }
        return newhead.next;
        

    }
}

第六题：143. 重排链表

缝缝补补的代码：本质还是每次往后找最后一个节点，插入。所以就是查找，插入。需要好多的if来判断是不是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 void reorderList(ListNode head) {
        if(head==null||head.next==null){
            return;
        }
        ListNode newHead = new ListNode(0, head);
        ListNode iter = head, target = head;
        while(iter.next!=null){
            target = iter;
            if(target.next.next==null)
                break;
            while(target.next.next!=null){
                target = target.next;
            }
            System.out.println(target.next.val);
            target.next.next = iter.next;
            iter.next =  target.next;
            target.next = null;
            if(iter.next==null || iter.next.next==null){
                break;
            }
            iter = iter.next.next;
        }

        

    }
}

第七题：160. 相交链表

最暴力的思路，当然还是会思考能不能O(n)时间内解决。

/**
 * 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) {
        ListNode a = headA, b = headB;
        while(a!=null){
            b = headB;
            while(b!=null){
                if(a==b){
                    return a;
                }
                b = b.next;
            }
            a=a.next;
        }
        return null;
        
    }
}

有大神的解法：https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/10774/tu-jie-xiang-jiao-lian-biao-by-user7208t
挺难想到的。

复习指南：看灵茶山艾府的基础精讲对应的视频。（翻转+快慢指针）
重点复习重排链表：设计反转和找中心节点（快慢指针）

class Solution {
    public void reorderList(ListNode head) {
        ListNode mid = middleNode(head);
        ListNode head2 = reverseList(mid);
        while (head2.next != null) {
            ListNode nxt = head.next;
            ListNode nxt2 = head2.next;
            head.next = head2;
            head2.next = nxt;
            head = nxt;
            head2 = nxt2;
        }
    }

    // 876. 链表的中间结点
    private ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 206. 反转链表
    private ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}