链表

链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过指针相连接。指针记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。

链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。

单链表的实现

template<class T>
class SLList {
public:
    // 构造函数
    SLList() : head(nullptr) {}

    // 打印链表元素
    void printSLList();

    // 增删成员函数
    // 尾插
    void push_back(T t);

    // 前插
    void push_front(T t);

    // 尾删
    void pop_back();

    // 前删
    void pop_front();

    // 在第一个指定位置后插入一个数据（后插）
    void insert(T pos, T t);

    // 在第一个指定位置删除一个数据
    void erase(T pos);

    // 析构函数
    ~SLList() {
        ListNode *node = head;
        while (node != nullptr) {
            ListNode *temp = node->next;
            delete node;
            node = temp;
        }
    }

    class ListNode {
    public:
        ListNode *next; // 指针域
        T data;         // 数据域
        ListNode(T x) : next(nullptr), data(x) {}
    };

    void append(SLList<T> &l) {
        if (!l.head) return; // 如果l为空，则什么也不做
        // 找到当前链表的最后一个节点
        ListNode *node = head;

        while (node->next != nullptr) {
            node = node->next;
        }
        // 将当前链表的最后一个节点的下一个指向l的第一个节点
        node->next = l.head;
    }

private:
    ListNode *head;
};

template<class T>
void SLList<T>::printSLList() {
    ListNode *node = head;
    while (node != nullptr) {
        cout << node->data << " -> ";
        node = node->next;
    }
    cout << "nullptr";
}

template<class T>
void SLList<T>::push_back(T t) {
    ListNode *node = head;
    ListNode *newnode = new ListNode(t);
    // 检查头节点是否为空
    // 头节点为空
    if (node == nullptr)
        head = newnode;
        // 头节点非空
    else {
        while (node->next != nullptr) {
            node = node->next;
        }
        node->next = newnode;
    }
}

template<class T>
void SLList<T>::push_front(T t) {
    // 与尾插类似
    ListNode *node = head;
    ListNode *newnode = new ListNode(t);
    if (head != nullptr) {
        newnode->next = node;
    }
    head = newnode;
}

template<class T>
void SLList<T>::pop_back() {
    ListNode *node = head;
    if (node == nullptr || node->next == nullptr) {
        head = nullptr;
        return;
    }
    while (node->next->next != nullptr) {
        node = node->next;
    }
    delete node->next;
    node->next = nullptr;
}

template<class T>
void SLList<T>::pop_front() {
    ListNode *node = head;
    if (node == nullptr || node->next == nullptr) {
        head = nullptr;
        return;
    }
    head = head->next;
    delete node;
}

template<class T>
void SLList<T>::insert(T pos, T t) {
    ListNode *node = head;
    ListNode *newnode = new ListNode(t);
    if (head == nullptr)
        return;
    if (head->data == pos) {
        newnode->next = head->next;
        head->next = newnode;
        return;
    }
    while (node->next != nullptr) {
        node = node->next;
        if (node->data == pos)
            break;
    }
    newnode->next = node->next;
    node->next = newnode;
}

template<class T>
void SLList<T>::erase(T pos) {
    // 指定位置数据
    ListNode *node = head;
    if (head == nullptr || head->data == pos)
        return;
    while (node->next->next != nullptr) {
        node = node->next;
        if (node->next->data == pos)
            break;
    }
    ListNode *tempnode = node->next;
    node->next = tempnode->next;
    delete tempnode;
}


void testSLList() {
    SLList<int> slList;
    // slList.push_back(100);
    // slList.push_back(200);
    slList.push_back(999);
    slList.push_back(888);
    slList.push_back(777);
    slList.insert(999, 666);
    // 999 -> 666 -> 888 -> 777 -> nullptr
    slList.erase(888);
    SLList<int> l;
    l.push_back(1222);
    l.push_back(123);
    l.push_back(12222);
    l.push_back(3333);
    slList.append(l);
    slList.printSLList();

}

链表算法题

移除链表元素

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

• 未设置哨兵位dummy

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 特殊情况1：头指针为空
        if (head == nullptr)
            return head;
        // 特殊情况2：头指针为连续的目标移除元素
        while (head != nullptr && head->val == val) {
            head = head->next;
        }
        // 规范化：cur,prev,next;
        ListNode* prev = nullptr;
        ListNode* cur = head;
        // 先考虑常规情况：
        while (cur != nullptr) {
            if (cur->val == val) {
                prev->next = cur->next;
                cur = prev->next;
            } else {
                prev = cur;
                cur = cur->next;
            }
        }
        return head;
    }
};

• 设置哨兵位

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 增加虚拟头节点（哨兵位）
        ListNode* dummy = new ListNode(0, head);
        ListNode* prev = dummy;
        while (prev->next != nullptr) {
            if (prev->next->val == val)
                prev->next = prev->next->next;
            else
                prev = prev->next;
        }
        return dummy->next;
    }
};

反转链表

描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表的头节点

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
};

相交链表

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

• 常规思路

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* head1 = headA;
        ListNode* head2 = headB;
        int count1 = 0;
        int count2 = 0;
        while (head1) {
            head1 = head1->next;
            count1++;
        }
        while (head2) {
            head2 = head2->next;
            count2++;
        }
        // headA 比 headB 长
        if (count1 > count2) {
            for (int i = 0; i < count1 - count2; i++)
                headA = headA->next;
        } else if (count1 < count2) {
            for (int i = 0; i < count2 - count1; i++)
                headB = headB->next;
        }
        while (headA != nullptr) {
            if (headA == headB)
                return headA;
            else {
                headA = headA->next;
                headB = headB->next;
            }
        }
        return nullptr;
    }
};

• 快慢指针

与判断链表中是否有环的思路相似

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (!headA || !headB) {
            return nullptr;
        }
        ListNode* head1 = headA;
        ListNode* head2 = headB;
        while (head1 != head2) {
            head1 = head1 == nullptr ? headB : head1->next;
            head2 = head2 == nullptr ? headA : head2->next;
        }
        return head1;
    }
};

交换链表

描述：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* cur = dummy;

        while (cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* temp1 = cur->next;
            ListNode* temp2 = temp1->next->next;
            cur->next = temp1->next;
            temp1->next->next = temp1;
            temp1->next = temp2;
            cur = cur->next->next;
        }
        return dummy->next;
    }
};

合并两个有序链表

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

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

# from cen

---