链表

链表的构建

链表主要有两种实现方式，第一种是Leetcode上的实现方式，使用new创建新节点，速度慢，使用指针操作。第二种是数组模拟链表，速度较快，但是面试中一般不会使用这种。

链表的基本操作

链表的基本操作有：在头结点之前插入节点、在头结点之后的某个节点之前插入数据、删除某个节点。

//Leetcode的节点定义
struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

//删除某个节点
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        //使用有哑节点处理删除头结点的情况
        ListNode *h = new ListNode(-1);
        h -> next = head;
        ListNode *pre = h, *p = pre -> next;
        //使用pre节点可以减少一次遍历，直接将两个指针到应有的位置
        while (p && p -> val != val) p = p -> next, pre = pre -> next;
        //判断一下边界情况，如果没有要查找的值就返回
        if (p == nullptr) return head;
        //核心语句，将pre的下一个指向p的下一个，相当于跳过了p
        pre -> next = p -> next;
        return h -> next;
    }
};

//在链表头插入节点
ListNode * add(ListNode *head, int x)
{
    ListNode *t = new ListNode(x);
    t -> next = head;
    return t;
}

//在链表中按照大小顺序插入节点
ListNode * addPos(ListNode* head, int x)
{
    //哑节点
    ListNode *h = new ListNode(-1);
    h -> next = head;
    ListNode *p = h;
    //遍历到某个节点的下一个如果值还是大于当前节点，并且不为空就继续
    while (p -> next && p -> next -> val < x) p = p -> next;
    //新建一个节点，赋值
    ListNode *t = new ListNode(x);
    //核心语句，将p的后边插入当前新节点t，以为有哑结点，所以相当于在head之前插入也是可以的
    t -> next = p -> next;
    p -> next = t;

    return h -> next;
}

//Acwing中使用数组模拟链表的模板
const int N = 100010;
//单链表定义，h = -1
int e[N], ne[N], idx;
int h = -1;
//双向链表定义
int e[N], r[N], l[N], idx;
int head = 0, tail = 1;

//单链表添加元素到链表头
void add_to_head(int x)
{
    e[idx] = x, ne[idx] = h, h = idx ++ ;
}
//单链表删除插入时的第k + 1个元素,需要特殊判断头节点删除的情况
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

//双向链表初始化
void init()
{
    r[0] = 1, l[1] = 0;
    idx = 2;
}

//双向链表添加元素第k个元素右边
void insert(int k, x)
{
    e[idx] = x;
    //将idx元素左边就是第k个，右边元素是k原来右边的元素
    l[idx] = k, r[idx] = r[k];
    //右边元素是r[k],其向左的指针l[r[k]]是现在的idx
    //k现在右边的是idx
    l[r[k]] = idx, r[k] = idx ++ ;
}

//删除输入的第k个数
void remove(int k)
{
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

例题

LC.147 对链表进行插入排序（中等）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//不带哑结点的原地插入
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head || !head -> next) return head;

        ListNode* p = head -> next;
        while (p)
        {
            ListNode* t = p;
            p = p -> next;
            ListNode* pre = head;
            while (pre -> next != t) pre = pre -> next;
            pre -> next = t -> next;
            //要判断一下是否要插入到头节点之前
            if (t -> val <= head -> val)
            {
                t -> next = head;
                head = t;
            }
            //如果需要插入到头结点之后，判断当前节点的下一个值是否还是小于当前插入节点值，如果小于则还需要再向前走一个位置
            else
            {
                ListNode* s = head;
                while (s -> next != p && s -> next -> val < t -> val) s = s -> next;
                t -> next = s -> next;
                s -> next = t;
            }
        }

        return head;
    }
};

//带哑结点的插入，省去的判断是否是链表头的操作
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head || !head -> next) return head;

        ListNode *h = new ListNode(-1);
        ListNode *p = head -> next;
        h -> next = head;
        head = h;

        //因为有哑结点存在，所以不需要判断头结点
        while (p)
        {
            ListNode *t = p;
            p = p -> next;
            ListNode *pre = head;
            while (pre -> next != t) pre = pre -> next;
            pre -> next = t -> next;

            ListNode *s = head;
            while (s -> next != p && s -> next -> val < t -> val) s = s -> next;
            t -> next = s -> next;
            s -> next = t;
        }

        return head -> next;
    }
};

//直接新建链表，挨个插入，省去删除操作
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head || !head -> next) return head;

        ListNode *h = new ListNode(-1);
        ListNode *p = head;
        while (p)
        {
            ListNode *t = p;
            p = p -> next;

            ListNode *s = h;
            while (s -> next && s -> next -> val < t -> val) s = s -> next;
            t -> next = s -> next;
            s -> next = t;
        }

        return h -> next;
    }
};

LC.剑指offer24.反转链表（简单）

反转链表要熟悉递归和迭代两种方式，递归写起来很优美，但是有些复杂，迭代需要更多的指针。

//递归方式，简洁但是得稍微思考一下边界条件和每一步所做的修改顺序
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head -> next) return head;
        ListNode *h = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = nullptr;
        return h;
    }
};
//迭代方式（哑节点），最简单无脑的方式，新建一个链表，每次头插
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head -> next) return head;
        ListNode *h = new ListNode(-1);
        while (head)
        {
            ListNode *t = head;
            head = head -> next;
            t -> next = h -> next;
            h -> next = t;
        }

        return h -> next;
    }
};
//迭代方式（原地修改），效率比较低，每次使用三个指针，认为第一个指针pre最开始指向nullptr
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head -> next) return head;

        ListNode * pre = nullptr, *cur = head;
        while (cur)
        {
            ListNode * nxt = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = nxt;
        }

        return pre;
    }
};

LC.相交链表（简单）

//基础方法，将长的加到短的长度，再去判断
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr;
        int lena = 0, lenb = 0;
        ListNode *p = headA, *q = headB;
        while (p) p = p -> next, lena ++ ;
        while (q) q = q -> next, lenb ++ ;

        while (lena > lenb) headA = headA -> next, lena --;
        while (lena < lenb) headB = headB -> next, lenb --;

        while (headA && headA != headB) headA = headA -> next, headB = headB -> next;
        return headA;
    }
};

//双指针算法，要将空指针看做两个链表一定相交的地方，并且空指针是真实能走到可停留的位置
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr;
        ListNode *a = headA, *b = headB;
        while (a != b)
        {
            if (!a) a = headB;
            else a = a -> next;
            if (!b) b = headA;
            else b = b -> next;
        }

        return a;
    }
};

LC.876 链表的中间节点（简单）

//快慢指针经典应用
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *fast = head, *slow = head;
        while (fast && fast -> next)
        {
            slow = slow -> next;
            fast = fast -> next -> next;
        }

        return slow;
    }
};

LC.回文链表（简单）

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *fast = head, *slow = head;
        //快慢指针寻找链表中点
        while (fast && fast -> next)
        {
            slow = slow -> next;
            fast = fast -> next;
            if (fast) fast = fast -> next;
        }

        ListNode *r = reverse(slow);

        //从两端开始依次比较，如果有一个方向的指针空了，表示两指针已经相遇
        ListNode *l = head;
        while (l && r)
        {
            if (l -> val != r -> val) return false;
            l = l -> next, r = r -> next;
        }

        return true;
    }

    //反转链表
    ListNode *reverse(ListNode *head)
    {
        if (!head || !head -> next) return head;
        ListNode *h = reverse(head -> next);
        head -> next -> next = head;
        head -> next = nullptr;

        return h;
    }
};