MyNote

[TOC]

707设计链表 

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将不会插入到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
`0 <= index, val <= 1000

单链表(singly list) 

class MyLinkedList {
private:
    struct Node {//单链表结点的定义
        int val;
        Node* next;
        Node(int v = 0, Node* n = nullptr) :val(v), next(n)
        {}
    };
    int size;//结点的个数
    Node* dummyHead;//头结点
public:
    MyLinkedList() {//构造函数
        size = 0;
        dummyHead = new Node();
    }
    //得到下标为index的结点的值
    //如果index无效，返回-1
    int get(int index) {
        if (index >= size) return -1;
        Node* curNode = dummyHead->next;
        while (index--) {//执行index次，cur在下标为index的结点
            curNode = curNode->next;
        }
        return curNode->val;
    }
    void addAtHead(int val) {
        Node* newNode = new Node(val);//构造新结点
        newNode->next = dummyHead->next;//新结点的next指向head的next
        dummyHead->next = newNode;//头结点的next指向新结点
        size++;
    }
    void addAtTail(int val) {
        Node* newNode = new Node(val);
        Node* curNode = dummyHead;//游标结点，用来遍历
        while (curNode->next) {//执行完后curNode在最后一个结点
            curNode = curNode->next;
        }
        curNode->next = newNode;
        size++;
    }
    //插入到下标为index的结点之前
    void addAtIndex(int index, int val) {
        if (index > size) return;//如果index比长度更大，不添加
        if (index == size) { addAtTail(val); return; }//如果index=链表的长度，尾添加
        Node* curNode = dummyHead;
        while (index--) {//执行index次，cur在下标为index的结点的前一个结点
            curNode = curNode->next;
        }
        //在curNode之后插入newNode
        Node* newNode = new Node(val);
        newNode->next = curNode->next;
        curNode->next = newNode;
        size++;
    }
    //如果下标有效，删除下标为index的结点
    void deleteAtIndex(int index) {
        if (index >= size) return;
        Node* curNode = dummyHead;
        while (index--) {//执行index次，cur在下标为index的结点的前一个结点
            curNode = curNode->next;
        }
        curNode->next = curNode->next->next;
        size--;
    }
};
/**
 * 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);

双向链表(doubly linkedList) 

class MyLinkedList {
private:
    struct Node {
        Node *pre;
        Node *next;
        int val;
        Node(int val) : val(val), pre(nullptr), next(nullptr) {};
    };
    Node *dummyHead;
    Node *dummytTail;
    int size;
public:
    MyLinkedList() : dummyHead(new Node(-1)), 
                    dummytTail(new Node(-1)), 
                    size(0) {
        dummyHead->next = dummytTail;
        dummytTail->pre = dummyHead;
    }
    
    int get(int index) {
        if (index >= size) return -1;
        Node *p = dummyHead->next;
        while (index--) {
            p = p->next;
        }
        return p->val;
    }
    
    void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    void addAtIndex(int index, int val) {
		if (index > size) return;
		Node* p = dummyHead->next;
		while (index--) {//执行index次数，p是下标为index的Node
			p = p->next;
		}
		Node* newNode = new Node(val);
		newNode->pre = p->pre;
		newNode->next = p;
		p->pre->next = newNode;
		p->pre = newNode;
		size++;
	}
    
    void deleteAtIndex(int index) {
        if (index >= size) return;
        Node *p = dummyHead->next;
        while (index--) {
            p = p->next;
        }
        p->pre->next = p->next;
        p->next->pre = p->pre;
        size--;
    }
};
/**
 * 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);
 */

链表中的双指针 

141环形链表 

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr||head->next==nullptr) return false;
        ListNode* slow=head;ListNode* fast=head;
        while(fast&&fast->next){
            slow=slow->next;
            fast=fast->next->next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
};

142环形链表2 

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return nullptr;
		ListNode *pFast = head, *pSlow = head, *ptr = head;
		while (pFast&&pFast->next) {
			pFast = pFast->next->next;
			pSlow = pSlow->next;
			if (pFast == pSlow) {//第一轮相遇
				while (pSlow != ptr) {//slow从相遇的地方走
					ptr = ptr->next;
					pSlow = pSlow->next;
				}
				return ptr;
			}
		}
		return nullptr;
    }
};

java

    public ListNode detectCycle(ListNode head) {
        ListNode fast=head,slow = head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow = slow.next;
            if(fast==slow)//有环
                break;
        }
        if(fast==null||fast.next==null){//无环
            return null;
        }
        //慢指针或快指针指向头节点
        fast = head;
        //两个指针都一步一步走, 相遇的地方就是
        while(fast!=slow){
            fast=fast.next;
            slow= slow.next;
        }
        return fast;
    }

160相交链表 

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须保持其原始结构。

自定义评测：

评测系统的输入如下（你设计的程序不适用此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr;
		ListNode *pa = headA, *pb = headB;
		while(pa!=pb)
        {
            pa=(pa==nullptr)?headB:pa->next;//pa遍历完链表A就从头遍历链表B
            pb=(pb==nullptr)?headA:pb->next;//pb遍历完链表B就从头遍历链表A
        }
        return pa;
    }
};

19删除倒数第n个结点 

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

 //添加dummyHead，防止头删除特殊处理
 //pfast和plow中间隔了n个结点
 //最后fast=nullptr时，plow就是要删除结点的前一个结点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead=new ListNode(0,head);
        ListNode* pfast=dummyHead;ListNode* plow=dummyHead;
        for(int i=0;i<n+1;i++){
            pfast=pfast->next;
        }
        while(pfast){
            plow=plow->next;
            pfast=pfast->next;
        }
        //删除plow之后的结点
        plow->next=plow->next->next;
        return dummyHead->next;
    }
};

java

    public ListNode removeNthFromEnd(ListNode head, int n) {
            //要删除倒数第n个节点，找到链表的倒数第n+1个节点
            //先用一个fast指针，走n+1步
            ListNode dummyHead = new ListNode(-1,head);
            ListNode fast = dummyHead;
            for(int i=0;i<n+1;i++){
                fast = fast.next;
            }
            //这时slow节点从开头出发，两个节点一起走
            ListNode slow = dummyHead;
            //走到待删除节点的前一个节点
            while(fast!=null){
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
            return dummyHead.next;
        }

21合并两个有序链表(可递归) 

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

 //双指针迭代，两个指针分别遍历list1和list2，较小的那个指针尾插到新链表，并前进一步
 //判断特殊情况，某个list先遍历完了或者某个list是空
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* p1=list1;
        ListNode* p2=list2;
        ListNode* pHead=new ListNode;
        ListNode* pTail=pHead;
        while(p1&&p2){
            ListNode* temp1=p1->next;
            ListNode* temp2=p2->next;
            if(p1->val < p2->val){//p1尾插到新链表，p1前进一步
                pTail->next=p1;
                pTail=p1;
                p1=temp1;
            }else{//p2尾插到新链表，p2前进一步
                pTail->next=p2;
                pTail=p2;
                p2=temp2;
            }
        }
        //特殊情况，某个list先遍历完了
        p1==nullptr?pTail->next=p2:pTail->next=p1;
        ListNode* res=pHead->next;
        delete pHead;
        return res;
    }
};

java

//双指针
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;

        ListNode p1 = list1,p2=list2;
        while(p1!=null&&p2!=null){
            if(p1.val<p2.val){//把较小的，尾插到新链表
                tail.next = p1;
                tail = p1;
                p1 =  p1.next;
            }else{
                tail.next = p2;
                tail = p2;
                p2 =  p2.next;
            }
        }
        if(p1!=null) 
            tail.next = p1;
        if(p2!=null)
            tail.next = p2;
        return dummyHead.next;
    }

206反转链表 

//双指针迭代法，依次遍历每一个结点，同时改变指针的指向
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head||!head->next) return head;
        ListNode* prev=nullptr;
        ListNode* curr=head;
        while(curr){
            ListNode* temp=curr->next;//保存curr->next
            curr->next=prev;//反转
            prev=curr;//prev向前
            curr=temp;//curr向前
        }
        return prev;
    }
};

876链表的中间节点 

876. 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

java

    public ListNode middleNode(ListNode head) {
        //快慢指针，同时出发。fast走2步，slow走1步
        ListNode fast = head,slow = head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

2两数相加 

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

//定义一个类，实现链表的尾插。因为这个操作需要很频繁，所以封装在一个函数里
class SinglyList {
public:
    std::unique_ptr<ListNode> pHead;
    ListNode* pTail;
    //初始化列表从右到左
    SinglyList() : pTail(pHead.get()), pHead(std::make_unique<ListNode>(-1)) {}
    void push_back(int val) {
        auto newNode = std::make_unique<ListNode>(val);
        pTail->next = newNode.get();
        pTail = newNode.get();
        newNode.release();//释放智能指针的所有权
    }
};
//双指针迭代，注意有加起来大于等于10要进位
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* p1 = l1;
        ListNode* p2 = l2;
        SinglyList ls;
        int carry = 0;
        while (p1 && p2) {
            //sum+carry才是最终要构造的新节点的val
            int sumPcarry = p1->val + p2->val + carry;
            ls.push_back(sumPcarry % 10);//尾插新节点
            carry = sumPcarry / 10;//计算进位
            p1 = p1->next;p2 = p2->next;//遍历下一个结点
        }
        if (p1 == nullptr) {
            while (p2) {
                int sumPcarry = p2->val + carry;
                ls.push_back(sumPcarry % 10);
                carry = sumPcarry / 10;
                p2 = p2->next;
            }
        }else {
            while (p1) {
                int sumPcarry = p1->val + carry;
                ls.push_back(sumPcarry % 10);
                carry = sumPcarry / 10;
                p1 = p1->next;
            }
        }
        //最后别忘了多余的进位
        if (carry != 0) 
            ls.push_back(carry);       
        return ls.pHead->next;
    }
};

经典问题 

203移除链表元素 

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head==nullptr) return nullptr;
        ListNode* dummyHead=new ListNode(-1,head);
        ListNode* curr=dummyHead;
        while(curr->next){
            if(curr->next->val==val){//判断curr->next
                curr->next=curr->next->next;
            }
            else curr=curr->next;
        }
        curr=dummyHead->next;
        delete dummyHead;dummyHead=nullptr;
        return curr;
    }
};

234回文链表 

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head) return false;
        if (!head->next) return true;
		//把链表放数组里
		ListNode *cur = head;
		vector<int> vec;
		while (cur) {
			vec.push_back(cur->val);
			cur = cur->next;
		}
		//判断回文
		for (int i = 0, j = (int)vec.size() - 1; i < j; ++i, --j) {
            if (vec[i] != vec[j]) {
                return false;
            }
        }
        return true;
    }
};

328奇偶链表 

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是奇数，第二个节点的索引为偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

输入: head = [1,2,3,4,5]输出: [1,3,5,2,4]

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head==nullptr||head->next==nullptr) return head;
        ListNode* curr=head;
        ListNode* oddDummyH=new ListNode(-1);
        ListNode* evenDummyH=new ListNode(-1);
        ListNode* oddTail=oddDummyH;
        ListNode* evenTail=evenDummyH;
        int num=1;//下标为0是奇数，所以这里直接置为1
        while(curr){
            ListNode* newNode=new ListNode(curr->val);
            if(num%2!=0){//奇数, 尾插法构造新链表
                oddTail->next=newNode;
                oddTail=newNode;
            }else{
                evenTail->next=newNode;
                evenTail=newNode;
            }
            num++;
            curr=curr->next;
        }
        oddTail->next=evenDummyH->next;
        ListNode* res=oddDummyH->next;
        delete oddDummyH;delete evenDummyH;
        return res;
    }
};

//改进：双指针一次迭代完成
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head==nullptr||head->next==nullptr) return head;
        ListNode* oddHead=head;//odd链表头
        ListNode* evenHead=head->next;//even链表头
        ListNode* tmp=evenHead;//记录偶数链表头，以便最后连接
        while(oddHead->next&&evenHead->next){//奇偶链表头都指向下下位，然后都向后走2步
            oddHead->next=evenHead->next;
            oddHead = oddHead->next;
            evenHead->next=oddHead->next;
		    evenHead = evenHead->next;
        }
        oddHead->next=tmp;//奇数链表的末尾和偶数链表头连接起来
        return head;
    }
};

中等 

138复制带随机指针的链表 

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。你的代码只接受原链表的头节点 head 作为传入参数。

提示：

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

//先不管random，尾插法把新链表构造出来.
//根据新旧链表对应关系的哈希表，把random填充
class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*,Node*> old2new;
        Node* dummyHead=new Node(-1);
        Node* pTail=dummyHead;
        Node* curr=head;
        while(curr){//遍历旧的链表
            Node* newNode=new Node(curr->val);
            pTail->next=newNode;pTail=newNode;
            old2new[curr]=newNode;//记录新旧链表一一对应的关系
            curr=curr->next;
        }
        curr=dummyHead->next;
        Node* oldP=head;
        while(curr){//遍历新链表和旧链表填充random
            curr->random=old2new[oldP->random];
            curr=curr->next;
            oldP=oldP->next;
        }
        return dummyHead->next;
    }
};

61旋转链表 

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

//所有结点往右k，相当于头尾双指针都往左k
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head||k==0) return head;
        ListNode* curr=head;
        int size=0;
        while(curr->next){//循环完curr在最后一个结点
            size++;
            curr=curr->next;
        }
        size++;//链表中结点的个数
        curr->next=head;//形成循环链表
        ListNode* pHead=head;ListNode* pTail=curr;
        int step=size-k%size;//计算步数是关键
        while(step--){//循环完之后的curr是新head
            pHead=pHead->next;pTail=pTail->next;
        }
        pTail->next=nullptr;//断开循环
        return pHead;
    }
};

优先队列 

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

java

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null||lists.length==0) return null;
        //放入优先队列 设置比较规则
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,
                (n1,n2)->n1.val - n2.val);
        for (ListNode list : lists) {
            if(list!=null)//que不能存null
                pq.add(list);
        }
        ListNode dummyHead = new ListNode();
        ListNode tail  = dummyHead;
        while(!pq.isEmpty()){
            //优先出队的是最小的
            ListNode poll = pq.poll();
            //加到新链表
            tail.next = poll;
            tail= tail.next;
            //继续入队
            if(poll.next!=null){
                pq.add(poll.next);
            }
        }
        return dummyHead.next;
    }

02_note

03_homework

day10_html

04_other

05_other_project

vue1

01_linux

02_nginx

03_docker

04_redis

05_SpringCloud-1

06_SpringCloud-2

07_基础技术

08_ 环境搭建

08_项目介绍

09_平台属性&品牌管理

10_spu

11_sku

12_商品详情页1

13_商品详情页2

14_elasticsearch-1

15_elasticsearch-2

16_首页 & 全文检索

17_单点登录

18. 购物车

19. RocketMQ

20. 订单

21. 支付

22. 支付后处理

23. 秒杀

仓储

707设计链表 &#8203;

单链表(singly list) &#8203;

双向链表(doubly linkedList) &#8203;

链表中的双指针 &#8203;

141环形链表 &#8203;

142环形链表2 &#8203;

160相交链表 &#8203;

19删除倒数第n个结点 &#8203;

21合并两个有序链表(可递归) &#8203;

206反转链表 &#8203;

876链表的中间节点 &#8203;

2两数相加 &#8203;

经典问题 &#8203;

203移除链表元素 &#8203;

234回文链表 &#8203;

328奇偶链表 &#8203;

中等 &#8203;

138复制带随机指针的链表 &#8203;

61旋转链表 &#8203;

优先队列 &#8203;

707设计链表

单链表(singly list)

双向链表(doubly linkedList)

链表中的双指针

141环形链表

142环形链表2

160相交链表

19删除倒数第n个结点

21合并两个有序链表(可递归)

206反转链表

876链表的中间节点

2两数相加

经典问题

203移除链表元素

234回文链表

328奇偶链表

中等

138复制带随机指针的链表

61旋转链表

优先队列