单链表

image.png
单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。

遍历链表

与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。

添加和删除操作

添加节点
image.png
与数组不同，我们不需要将所有元素移动到插入元素之后。因此，您可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。
添加头节点
众所周知，我们使用头结点来代表整个列表。
因此，在列表开头添加新节点时更新头结点 head 至关重要。

  1. 初始化一个新结点 cur ；
  2. 将新结点链接到我们的原始头结点 head。
  3. 将 cur 指定为 head 。

删除节点
image.png
删除头结点
image.png

设计单链表

实现如下

  1. /*
  2.  * @lc app=leetcode.cn id=707 lang=cpp
  3.  *
  4.  * [707] 设计链表
  5.  */
  7. // @lc code=start
  10. class Node
  11. {
  12. public:
  13.     int val;
  14.     Node *next;
  15.     Node(int x) : val(x), next(nullptr){}
  16. };
  19. class MyLinkedList {
  20. public:
  21.     MyLinkedList() {
  22.         head = new Node(0);  // initialize head node
  23.         size = 0;  // initialize LinkList size
  24.     }
  26.     int get(int index) {
  27.         if (index < 0 || index > size - 1) return -1;
  28.         Node* cur = head->next;
  29.         while (index--) cur = cur->next;
  30.         return cur->val;
  31.     }
  33.     void addAtHead(int val) {
  34.         Node* newHead = new Node(val);
  35.         newHead->next = head->next;
  36.         head->next = newHead;
  37.         size++;
  38.     }
  40.     void addAtTail(int val) {
  41.         Node* cur = head;
  42.         while (cur->next) cur = cur->next;  // get the last node
  43.         Node* newNode = new Node(val);
  44.         cur->next = newNode;  // link the newNode;
  45.         size++;
  46.     }
  48.     void addAtIndex(int index, int val) {
  49.         if (index <= 0) addAtHead(val);
  50.         else if (index == size) addAtTail(val);
  51.         else if (index > size) return;
  52.         else
  53.         {
  54.             Node* newNode = new Node(val);
  55.             Node* cur = head;
  56.             while (index--) cur = cur->next;
  57.             newNode->next = cur->next;
  58.             cur->next = newNode;
  59.             size++;
  60.         }
  61.     }
  63.     void deleteAtIndex(int index) {
  64.         if (index < 0 || index >= size) return;
  65.         Node* cur = head;
  66.         while (index--) cur = cur->next;
  67.         cur->next = cur->next->next;
  68.         size--;
  69.     }
  70. private:
  71.     int size;  // length of listnode
  72.     Node* head;
  73. };
  75. /**
  76.  * Your MyLinkedList object will be instantiated and called as such:
  77.  * MyLinkedList* obj = new MyLinkedList();
  78.  * int param_1 = obj->get(index);
  79.  * obj->addAtHead(val);
  80.  * obj->addAtTail(val);
  81.  * obj->addAtIndex(index,val);
  82.  * obj->deleteAtIndex(index);
  83.  */
  84. // @lc code=end

题目：相交链表

image.png
解题思路：
解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。
如果用两个指针 p1 和 p2 分别在两条链表上前进，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

  1. /*
  2.  * @lc app=leetcode.cn id=160 lang=cpp
  3.  *
  4.  * [160] 相交链表
  5.  */
  7. // @lc code=start
  8. /**
  9.  * Definition for singly-linked list.
  10.  * struct ListNode {
  11.  *     int val;
  12.  *     ListNode *next;
  13.  *     ListNode(int x) : val(x), next(NULL) {}
  14.  * };
  15.  */
  16. class Solution {
  17. public:
  18.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  19.         ListNode *p1 = headA, *p2 = headB;
  20.         while (p1 != p2)
  21.         {
  22.             if (p1 == nullptr) p1 = headB;
  23.             else p1 = p1->next;
  24.             if (p2 == nullptr) p2 = headA;
  25.             else p2 = p2->next;
  26.         }
  27.         return p1;
  28.     }
  29. };
  30. // @lc code=end

另一种思路, 先获取两条链表的长度, 然后让p1 和 p2 距离链表尾部的距离相同

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int len_A = genLength(headA);
        int len_B = genLength(headB);
        int len;
        // make two listNode the same length
        if (len_A > len_B)
        {
            len = len_B;
            while (len_A-- > len_B) headA = headA->next;
        }
        else
        {
            len = len_A;
            while (len_B-- > len_A) headB = headB->next;
        }

        // move together
        while(len--)
        {
            if (headA == headB) return headA;
            headA = headA->next;
            headB = headB->next;
        }
        return nullptr;
    }
private:
    int genLength(ListNode *head)
    {
        int size = 0;
        while (head != nullptr)
        {
            head = head->next;
            size++;
        }
        return size;
    }
};

题目：删除链表的倒数第N个节点

image.png
解题思路：
先获取链表长度， 倒数第N个节点就是第 len - n - 1个节点
实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int index = genLength(head) - n - 1;
        if (index < 0) return head->next;
        ListNode* pre = head;
        while(index--) pre = pre->next;
        pre->next = pre->next->next;
        return head;
    }
private:
    int genLength(ListNode* head)
    {
        int size = 0;
        while (head != nullptr)
        {
            head = head->next;
            size++;
        }
        return size;
    }
};

双链表

image.png

设计双链表

/*
 * @lc app=leetcode.cn id=707 lang=cpp
 *
 * [707] 设计链表
 */

// @lc code=start

class Node
{
public:
    int val;
    Node *next, *pre;
    Node(int x) : val(x), next(nullptr), pre(nullptr) {}
};

class MyLinkedList {
public:
    MyLinkedList() {
        // 初始化头结点
        head = new Node(0);
        this->size = 0;
    }

    int get(int index) {
        if (index < 0 || index >= size) return -1;
        Node *cur = head->next;
        while (index--) cur = cur->next;
        return cur->val;
    }

    void addAtHead(int val) {
        Node *newNode = new Node(val);
        if (head->next) head->next->pre = newNode;
        newNode->next = head->next;
        newNode->pre = head;
        head->next = newNode;
        size++;
    }

    void addAtTail(int val) {
        Node *cur = head;
        Node *newNode = new Node(val);
        while(cur->next) cur = cur->next;
        cur->next = newNode;
        newNode->pre = cur;
        newNode->next = nullptr;
        size++;
    }

    void addAtIndex(int index, int val) {
        if (index <= 0) addAtHead(val);
        else if (index == size) addAtTail(val);
        else if (index > size) return;
        else
        {
            Node *cur = head->next, *newNode = new Node(val);
            while (index--) cur = cur->next;
            newNode->next = cur;
            newNode->pre = cur->pre;
            cur->pre->next = newNode;
            cur->pre = newNode;
            size++;
        }
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node *cur = head->next;
        while (index--) cur = cur->next;
        if (cur->next)
        {
            cur->next->pre = cur->pre;
            cur->pre->next = cur->next;
        }
        else cur->pre->next = nullptr;
        delete cur;
        size--;
    }
private:
    int size;
    Node *head;
};

/**
 * Your MyNode object will be instantiated and called as such:
 * MyNode* obj = new MyNode();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
// @lc code=end

题目: 合并有序链表

image.png

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
       if (!list1 || !list2) return !list1 ? list2 : list1;
        ListNode *node = new ListNode(0);
        ListNode *res = node;
        while (list1 != nullptr && list2 != nullptr)
        {
            if (list1->val > list2->val)
            {
                node->next = list2;
                list2 = list2->next;
            } 
            else
            {
                node->next = list1;
                list1 = list1->next;
            }
            node = node->next;
        }
        if (list1 != nullptr) node->next = list1;
        else if (list2 != nullptr) node->next = list2;
        return res->next;
    }
};

题目：旋转链表

image.png
解题思路：
image.png
image.png

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !k) return head;
        int n = 0;  // 链表长度
        ListNode *tail;  // 尾结点
        for (ListNode *p = head; p != nullptr; p = p->next)
        {
            tail = p;
            n++;
        }
        k %= n;
        ListNode *p = head;
        // 找到第n - k个节点
        for (int i = 0; i < n - k - 1; i++)
        {
            p = p->next;
        }
        tail->next = head;
        head = p->next;
        p->next = nullptr;
        return head;
    }
};