C++

链表

• 单链表

• 双链表

  • 每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点
  • 可以向前、向后查询

• 循环链表

  • 链表首尾相连
  • 可以用来解决约瑟夫环问题

链表的存储方式

在内存中非连续分布，分配机制取决与操作系统的内存管理

链表的定义

// 单链表
struct ListNode {
  int val;
  ListNode* next;
  ListNode(int x) : val(x), next(nullptr) {}  // 节点的构造函数
};

注意：如果不定义节点的构造函数，则C++默认生成一个构造函数。但是初始化时无法直接给变量赋值

ListNode *head = new ListNode(5);  // 使用自己的构造函数
ListNode *head = new ListNode();  // 默认构造函数
head->val = 5;

性能分析

名称 空间复杂度 时间复杂度 适用场景
数组 O(n) O(1) 数据量固定，频繁查询，较少增删
链表 O(1) O(n) 数据量不固定，频繁增删，较少查询

leetcode203

// 移除链表元素
#include <iostream>
using namespace std;

struct ListNode {
  int val;
  ListNode *next;
  //ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
 public:
  ListNode* remove_elements(ListNode* head, int val) {
    // 直接使用链表进行操作
    /*
    // 删除头节点
    while (head != NULL && head->val == val) {
      ListNode* tmp = head;
      // 头节点后移
      head = head->next;
      // 删除原来的头节点
      delete tmp;
    }
    // 删除非头节点
    ListNode* cur = head;
    // 这里如果cur时最后一个节点，且正好 == val，就会进行上面的while循环
    while (cur != NULL && cur->next != NULL) {
      if (cur->next->val == val) {
        ListNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
      } else {
        cur = cur->next;
      }
    }
    return head;
    */



    // 设置虚拟头节点，进行移除操作
    ListNode* dummyHead = new ListNode(0);
    dummyHead->next = head;
    ListNode* cur = dummyHead;
    while (cur->next != NULL) {
      if (cur->next->val == val) {
        // 删除符合条件的节点
        ListNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
      } else {
        // 当前节点右移
        cur = cur->next;
      }
    }
    // 将移除元素后的链表赋值给head
    head = dummyHead->next;
    // 删除虚拟头节点
    delete dummyHead;
    return head;
  }
};

int main() {
  Solution solution;
  int val = 5;
  ListNode* head = new ListNode(0);  // 是否有参数取决于构造函数
  // 链表填入数字
}

leetcode707

// 设计链表
#include <iostream>
using namespace std;

class MyLinkedList {
 public:
  // 定义链表节点结构体
  struct LinkedNode {
    int val;
    LinkedNode* next;
    LinkedNode(int x) : val(x), next(nullptr) {}
  };

  // initialize your data structure here
  MyLinkedList() {
    dummyHead_ = new LinkedNode(0);
    size_ = 0;
  }

  // get the value of the index-th node in the linked list. 
  // if the index is invalid, return -1
  int get(int index) {
    if (index > (size_ - 1) || index < 0) {
      return -1;
    }
    LinkedNode* cur = dummyHead_->next;
    while (index--) {
      cur = cur->next;
    }
    return cur->val;
  }

  // add a node of value val before the first element of the linkd list.
  // After the insertion, the new node will be the first node of the linked list
  void add_at_head(int val) {
    LinkedNode* newNode = new LinkedNode(val);  // 开空间
    newNode->next = dummyHead_->next;  // 新节点插入虚拟节点和第一个节点之间
    dummyHead_->next = newNode;
    size_++;
  }

  // append a node of value val to the last element of the linked list
  void add_at_tail(int val) {
    LinkedNode* newNode = new LinkedNode(val);  // 为新节点开空间
    LinkedNode* cur = dummyHead_;
    while (cur->next != nullptr) {
      cur = cur->next;  // cur为最后一个节点
    }
    cur->next = newNode;  // 将新节点作为cur的下一个节点
    size_++;  // 链表长度加1
  }

  // add a node of value val before the index-th node in the linked list. 
  // if index equals to the length of linked list, the node will be appended to the end of the linked list
  void add_index(int index, int val) {
    // index大于链表长度，返回空
    if (index > size_) {
      return;
    }
    LinkedNode* newNode = new LinkedNode(val);
    // cur从虚拟头节点开始，所以newNode插入到cur的后面
    LinkedNode* cur = dummyHead_;
    while(index--) {
      cur = cur->next;
    }
    newNode->next = cur->next;
    cur->next = newNode;
    size_++;
  }

  // delete the index-th node in the linked list, if the index is valid
  void delete_at_index(int index) {
    // index 不合法
    if(index >= size_ || index < 0) {
      return;
    }
    // cur从虚拟节点开始，所以在计算index时，默认少1，所以选择cur后面的节点
    LinkedNode* cur = dummyHead_;
    while(index--) {
      cur = cur->next;
    }
    LinkedNode* tmp = cur->next;
    cur->next = cur->next->next;
    // 删除该节点，释放内存
    delete tmp;
    size_--;
  }

  // 打印链表
  void print_linked_list() {
    LinkedNode* cur = dummyHead_;
    while (cur->next != nullptr) {
      cout << cur->next->val << " ";
      cur = cur->next;
    }
    cout << endl;
  }

 private:
  int size_;
  LinkedNode* dummyHead_;
};

leetcode206

// 反转链表
#include<iostream>
using namespace std;

class Solution {
  struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
  };

 public:
  ListNode* reverse_list(ListNode* head) {
    // 双指针法
    ListNode* tmp;  // cur的下一个节点
    ListNode* cur = head;
    ListNode* pre = NULL;
    while (cur) {
      tmp = cur->next;  // 下一个节点赋值给tmp，反转时要改变cur->next
      // 注意，这里虽然是将next变为pre，实际上是pre赋值给next
      cur->next = pre;  // 反转操作,将所有的next全部变为pre
      // 更新cur和pre指针
      pre = cur;
      cur = tmp;
    }
    return pre;
  }
};

leetcode24

// 两两交换链表中的节点
#include <iostream>
using namespace std;

class Solution {
 public:
  struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
  };

  // 建议画图, 主要是链表的指向变化
  ListNode* swap_pairs(ListNode* head) {
    ListNode* dummyHead = new ListNode(0);  // 设置虚拟头节点
    dummyHead->next = head;
    ListNode* cur = dummyHead;
    while (cur->next != nullptr && cur->next->next != nullptr) {
      ListNode* tmp = cur->next;  // 临时节点
      ListNode* tmp1 = cur->next->next->next;  // 临时节点
      cur->next = cur->next->next;
      cur->next->next = tmp;
      cur->next->next->next = tmp1;

      cur = cur->next->next;  // 准备下一轮交换
    }
    return dummyHead->next;
  }
};

leetcode19

// 删除倒数第n个节点
#include <iostream>
using namespace std;

class Solution {
 public:
  struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
  };

  ListNode* remove_n_from_end(ListNode* head, int n) {
    ListNode* dummyHead = new ListNode(0);  // 虚拟头节点
    dummyHead->next = head;
    // 快慢指针
    ListNode* fast = dummyHead;
    ListNode* slow = dummyHead;
    // fast指针先向后走n步
    while (n-- && fast != NULL) {
      fast = fast->next;
    }
    fast = fast->next;  // fast再提前走一步，让slow指向删除节点的上一个节点
    // 当fast指针不指向链表尾部时，fast和slow都向右移
    // fast指针和slow指针相差n+1个元素
    while (fast != NULL) {
      fast = fast->next;
      slow = slow->next;
    }
    // fast指向null,即slow+1是倒数第n个节点，进行删除
    slow->next = slow->next->next;
    return dummyHead->next;



    // 递归, 找到倒数第n个节点，对该节点进行操作
    /*
    if (!head) return NULL;
    head->next = removeNthFromEnd(head->next, n);
    cur++;  // 放在递归函数外面，就导致递归结束时，直接head指向了整个链表的最后一个节点，然后cur++，一层一层返回，类似套娃
    if (n == cur) return head->next;
    return head;
    */
  }
};

mianshi0207

/*
  给定两个单链表的头节点，找出并返回两个单链表相交的起始节点，否则返回null
*/
#include <iostream>
using namespace std;

class Solution {
 public:
  struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
  };

  ListNode* get_intersection_node(ListNode* headA, ListNode* headB) {
    // 朴素解法, 计算A、B链表的长度求差，长链表减去差后，两个链表一一对比
    ListNode* curA = headA;
    ListNode* curB = headB;
    int lenA = 0, lenB = 0;  // 节点长度
    while (curA != NULL) {  // 循环获取节点长度
      lenA++;
      curA = curA->next;
    }
    while (curB != NULL) {
      lenB++;
      curB = curB->next;
    }
    curA = headA;  // 节点还原
    curB = headB;
    // 让curA为最长链表的头, LenA为其长度
    if (lenB > lenA) {
      swap(lenA, lenB);
      swap(curA, curB);
    }
    int gap = lenA - lenB;  // 获取长度差
    while (gap--) {
      curA = curA->next;  // 调整长链表，使两个链表对齐
    }
    while (curA != NULL) {  // 循环寻找相同的节点
      if (curA == curB) {
        return curA;
      }
      curA = curA->next;
      curB = curB->next;
    }
    return NULL;

    
    
    /* 花里胡哨解法
    // 两个链表未相交部分长度为a, b, 相交部分长度为c
    // 链表1 = a+c, 链表2 = b+c
    // a + c + b = b + c + a,即表1走表2的路，表2走表1的路，最终到达同一个节点
    
    ListNode* a = headA;
    ListNode* b = headB;
    // 如果相同，则遇到相等的节点了，否则走完a,b，最后都指向NULL
    while (a != b) {
      a = (a != NULL ? a->next : headB);  // 先走表a，再走表b
      b = (b != NULL ? b->next : headA);  // 先走表b，再走表a
    }
    return a;
    */
  }
};

leetcode142

// 环形链表II
#include <iostream>
using namespace std;

class Solution {
 public:
  struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
  };

/*
快慢指针fast移动2次，slow移动一次，如果有环，俩个指针一定会在环中相遇
设头节点到入环点的节点数为x，入环点到相遇点节点数为y，相遇点到入环点的距离为z
则fast = x + y + n(y+z); slow = x + y; 又fast = 2 * slow
即 x = (n-1)(y+z) + z 成立
再设两个指针，分别代表等式两边的节点，两个指针的相遇点就是环形入口节点
*/

  ListNode* detect_cycle(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast != NULL && fast->next != NULL) {
      slow = slow->next;
      fast = fast->next->next;  // 快节点一次移动两个节点
      if (slow == fast) {  // 快慢节点相遇，说明有环
        ListNode* index1 = fast;  // 数学推导的x
        ListNode* index2 = head;  // 数学推导的(n-1)(y+z) + z
        while (index1 != index2) {  // 两个指针移动相同距离后相遇点为环形入口点
          index1 = index1->next;
          index2 = index2->next;
        }
        return index1;
      }
    }
    return NULL;
  }
};

本文由 szr 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Sep 23, 2021 at 10:12 am