数据结构——线性表（链表，力扣简单篇）

一、链表的一些基本操作

1.1归并

1.1.1 升序+升序=升序【尾插法】

对于二路归并来说，将两个有序的线性表归并成一个。
链表并不需要开辟新的空间。

情况1：升序+升序=升序

• 对于链表1，用p指向当前链表。
• 对于链表2，用q指向当前链表。
• 若p->val < q->val，则将p连入链表：将p往后挪动一个。cur也向后移动一个。同理q也进行同样的操作。
• 当p==null，表示链表1已经完了，直接将链表2接到最终结果后就行了。q同理。
  

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if(list1==nullptr && list2==nullptr) return list1;
    //创建一个头结点和cur指针
    ListNode* dummy=new ListNode();
    ListNode* cur=dummy;
    ListNode* p=list1;
    ListNode* q=list2;
    //当两个链表都没遍历完时，进行比较操作，并移动指针
    while(p!=nullptr && q!=nullptr){
        if(p->val <= q->val){
        	//尾插法插入
            cur->next=p;
            //向后移动一个
            p=p->next;
            cur=cur->next;
        }else{
        	//尾插法插入
            cur->next=q;
            //向后移动一个
            q=q->next;
            cur=cur->next;
        }
    }
    //当其中有一个链表已经遍历完时：直接接入另一个链表
    if(p==nullptr) cur->next=q;
    if(q==nullptr) cur->next=p;
    return dummy->next;
}

1.1.2升序+升序=降序【头插法 or 反转】

情况2：升序+升序=降序

• 方法1：归并成升序后，反转链表
• 方法2：用两个指针p和q指向链表，比较链表的值，将较小的那个用头插法插入到dummy的后面即可。
  
  需要注意的是：头插法中必须先保存当前节点的下一个指针，否则会丢失原链表的后续节点。原代码：
• p->next=dummy->next;
• dummy->next=p;
• p=p->next;
  最后一个p=p->next; 此时再执行 p = p->next，p=dummy->next，而不是原链表中 p 的下一个节点。

while(p!=nullptr && q!=nullptr){
    if(p->val <= q->val){
     	//头插法插入
     	ListNode* pnext=p->next;
     	p->next=dummy->next;
     	dummy->next=p;
     	//向后
     	p=pnext;
    }else{
     	ListNode* qnext=q->next;
        //头插法插入
        q->next=dummy->next;
        dummy->next=q;
        //向后
        q=qnext;
    }
}
// 处理剩余节点：将剩余节点依次头插
while (p != nullptr) {
	ListNode* pnext=p->next;
    p->next = dummy->next;
    dummy->next=p;
    p=pnext;
}
while (q != nullptr) {
	ListNode* qnext=q->next;
    q->next = dummy->next;
    dummy->next = q;
    q = qnext;;
}

1.2反转

1.2.1反转整个链表【头插法】

反转1（反转整个链表）：将整个链表反转

使用头插法将整个链表重新插入，注意保存p的下一个指针 pnext。

需要注意的是：如果初始化dummy指向头结点，那么在第一次循环时，容易形成闭环。正常的1和2之间已经没有了联系，但是并不影响p的头插。

ListNode* reverseList(ListNode* head) {
        if(head==nullptr || head->next==nullptr) return head;
        
        ListNode* dummy=new ListNode();
        dummy->next=nullptr;//注意dummy初始指向空
        
        ListNode* p=head;
        while(p!=nullptr){
            ListNode* pnext=p->next;
            p->next=dummy->next;
            dummy->next=p;
            p=pnext;
        }
        return dummy->next;
    }

1.2.2反转部分链表【q后尾插】

反转2（反转部分链表）：给出指针 p 以及指针 q 指向链表中的某个节点。要求从 p->next 开始一直到 q 范围内的链表逆置。

• 记录一下p后面待反转的节点t
• 然后类似于将 t 从序列中删除，然后插入到 q 的后面。
• 当p->next==q 循环停止
  

ListNode* reverseList(ListNode* head) {
    if(head==nullptr || head->next==nullptr) return head;
    ListNode* dummy=new ListNode();
    dummy->next=head;
    ListNode* p=dummy;
    ListNode* q=dummy;
    while(q->next!=nullptr) q=q->next;
    
    while(p->next!=q){
        ListNode* t=p->next;//t必须写在里面
        p->next=t->next;
        t->next=q->next;
        q->next=t;
    }
    return dummy->next;
}

1.3双指针

1.3.1寻找中间节点

• 思路1：遍历链表，得到链表的长度，中间节点为 index=n/2 的节点
• 思路2：利用指针：快指针 fast 每次走 2 步。慢指针 slow 每次走 1 步
  • 对于6个元素的：快指针【1-3-5-null】，慢指针【1-2-3-4】。fast==null 结束
  • 对于7个元素的：快指针【1-3-5-7-null】，慢指针【1-2-3-4】。fast->next==null 结束。

while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;       // 慢指针走1步
    fast = fast->next->next; // 快指针走2步
}

1.3.2寻找倒数第N个节点

• 思路1：遍历链表，得到链表的长度，倒数第N个节点的下标应该为length-n，其前一个节点的下标为length-n-1。
• 思路2：慢指针和快指针之间相差k个节点。【先让 fast 指针走到下标为n-1的节点处】。当快指针走到终点时，慢指针所指的节点刚好就是倒数第N个节点。
  
  

int kthToLast(ListNode* head, int k) {
        ListNode* dummy=new ListNode();
        dummy->next=head;
        ListNode* fast=dummy;
        ListNode* slow=dummy;
        for(int i=0;i<=k-1;i++){
          fast=fast->next;
        }
        while(fast!=nullptr){
          fast=fast->next;
          slow=slow->next;
        }
        return slow->val;
    }

1.4 回文 & 环形 & 相交

1.4.1回文【数组】

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。

遍历整个数组，将val值存储在vector数组中。然后用双指针（头和尾）分别指向，判断，移动。

bool isPalindrome(ListNode* head) {
    vector<int> result;
    //将val存入result
    while(head!=nullptr){
        result.push_back(head->val);
        head=head->next;
    }
    //判断
    int left=0;
    int right=result.size()-1;
    while(left<right){
        if(result[left]==result[right]) {left++;right--;}
        else return 0;
    }
    return 1;
}

1.4.2环形【visited or 双指针】

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

• 思路1：遍历整个链表，然后看该节点是否已经被访问过了。用类似于visited数组来存储访问过的元素。
  • 若节点被访问过了：有环
  • 否则：没环，将当前节点加入数组。直到链表访问完成。

需要注意的是：unordered_set（无序）查找的时间复杂度为O（1），vector查找的时间复杂度为O（n）。

bool hasCycle(ListNode *head) {
    unordered_set<ListNode*> visited;
    while(head!=nullptr){
        if(visited.count(head)) return 1;
        else visited.insert(head);
        head=head->next;
    }
    return 0;
}

• 思路2：设计快慢指针。慢指针每次移动 1 步；快指针每次移动 2 步。初始slow=head fast=head。
• 若链表有环，当慢指针进入环后，快指针也会进入环并以更快的速度绕环移动，最终会追上慢指针（类似跑道上的套圈）。
  
  若链表无环，快指针会先于慢指针到达尾部。
  

bool hasCycle(ListNode *head) {
        if(head==nullptr || head->next==nullptr) return 0;
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast!=nullptr && fast->next!=nullptr){
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast) return 1;
        }
        return 0;
    }

1.4.3相交【遍历 or 长度对齐】

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

思路1：长度对齐法：

• 分别计算两个链表的长度 lenA 和 lenB。
• 让较长的链表的指针先移动 |lenA - lenB| 步，使两个指针处于 “同一起跑线”（距离各自链表尾部的长度相等）。
• 同时移动两个指针，若相遇则为相交节点；若同时到达尾部仍未相遇，则不相交。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(headA==nullptr && headB==nullptr) return nullptr;
    int lenA=getlength(headA);
    int lenB=getlength(headB);
    //调整指针位置至一样多
    ListNode* pA=headA;
    ListNode* pB=headB;
    if(lenA<lenB){
        for(int i=1;i<=lenB-lenA;i++){
            pB=pB->next;
        }
    }else{
        for(int i=1;i<=lenA-lenB;i++){
            pA=pA->next;
        }
    }
    //判断是否指向同样的节点
    while(pA!=nullptr && pB!=nullptr){
        if(pA==pB) return pA;
        else{
            pA=pA->next;
            pB=pB->next;
        }
    }
    return nullptr;
}

思路2：

• 遍历第一个链表，将所有节点的地址（指针）存入哈希表（如 unordered_set）。
• 遍历第二个链表，对每个节点检查是否在哈希表中存在：
  • 若存在，说明该节点是第一个相交节点，返回该节点。
  • 若遍历结束均不存在，说明两链表不相交，返回 null。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    unordered_set<ListNode*> nodes;
    while(headA!=nullptr){
        nodes.insert(headA);
        headA=headA->next;
    }
    while(headB!=nullptr){
        if(nodes.count(headB)) return headB;
        headB=headB->next;
    }
    return nullptr;
}

1.4.4二进制链表转换为整数

将对每一位数字乘以对应的幂指数就行了。

int getDecimalValue(ListNode* head) {
    long long sum=0;
    int l=getlength(head);

    for(int i=0;i<=l-1;i++){
        sum+=head->val * pow(2,l-i-1);
        head=head->next;
    }
    return sum;
}

优化1：
例：123（十进制）=【12】*10 + 【3】。将每次得到的sum * 进制 + val即可。

sum = sum * 2 + head->val; // 每一步等价于左移1位（×2）再加上当前值

sum = (sum << 1) | head->val; // 左移1位（×2）+ 当前位值