单链表翻转

#include <stdio.h>

struct ListNode {
    int val;
    ListNode* next;
};

// 单链表翻转
ListNode* func(ListNode* head) {
    ListNode* head2 = nullptr;
    while (head) {
        auto tmp = head->next;
        head->next = head2;
        head2 = head;
        head = tmp;
    }
    return head2;
}

一趟扫描完成从m到n的链表进行反转

// 一趟扫描完成从m到n的链表进行反转
ListNode* func(ListNode* head, int m, int n) {
    if (m <= 0 || n <= 0 || m >= n) {
        return head;
    }
    // 添加一个虚拟的头
    auto pre = new ListNode();
    pre->next = head;
    auto start = pre;
    for (int i = 0; i < m - 2; i++) {
        start = start->next;
    }
    auto back1 = start;    // 左段尾巴位置
    start = start->next;
    auto back2 = start;    // 中段起始位置
    // 通用翻转代码
    ListNode* then = nullptr;
    for (int i = 0; i < n - m + 1 && start; i++) {
        auto tmp = start->next;
        start->next = then;
        then = start;
        start = tmp;
    }
    back2->next = start;    // 中断起始位置接右段起始位置
    back1->next = then;     // 左段尾巴位置接中段末尾位置
    return pre->next;
}

链表中倒数第k个节点

struct ListNode {
    int val;
    ListNode* next;
};

// 倒数第k个元素
int func(ListNode* head, int k) {
    if (k <= 0) {
        return 0;
    }
    auto a = head;
    auto b = head;
    int dis = 0;
    while (b) {
        if (dis < k) {
            b = b->next;
            dis++;
        } else if (dis == k) {
            b = b->next;
            a = a->next;
        }
    }
    if (dis == k) {
        return a->val;
    }
    return 0;
}

扩展问题：
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。使用一趟扫描实现。

旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

思路：先变成循环链表，然后从头部开始数，指定个数，切断

// 旋转链表
ListNode* func(ListNode* head, int k) {
    if (k <= 0) {
        return head;
    }
    // 变成循环链表
    auto tmp = head;
    while (tmp->next)
    {
        tmp = tmp->next;
    }
    tmp->next = head;
    tmp = head;
    int i = 0;
    while (true) {
        auto at = tmp;
        if (i == k - 1) {
            tmp = at->next;
            at->next = nullptr;
            break;
        }
    tmp = at-&gt;next;
    i++;
}
return tmp;
}

检查单链表是否存在环

两个指针跑，有环必然遇见

bool func(ListNode* head) {
    auto a = head;
    auto b = head;
    while (b && b->next) {
        a = a->next;
        b = b->next->next;
        if (a == b) {
            return true;
        }
    }
    return false;
}

检查单链表是否存在环， 找到环的入口，没有返回空

寻找环入口的方法就是采用两个指针，一个从表头出发，一个从相遇点出发(2倍移速时的相遇点)，一次都只移动一步，当二者相等时便是环入口的位置

ListNode* func(ListNode* head) {
    auto a = head;
    auto b = head;
    bool find = false;
    while (b && b->next) {
        a = a->next;
        b = b->next->next;
        if (a == b) {
            find = true;
            break;
        }
    }
    if (!find) {
        return nullptr;
    }
    while (head != b) {
        head = head->next;
        b = b->next;
    }
    return head;
}

检查单链表是否存在环, 判断环大小

环的相遇点，再继续2倍速快慢跑，再次相遇的时候刚好一圈

int func(ListNode* head) {
    auto a = head;
    auto b = head;
    bool find = false;
    while (b && b->next) {
        a = a->next;
        b = b->next->next;
        if (a == b) {
            find = true;
            break;
        }
    }
    if (!find) {
        return 0;
    }
    a = b;
    int size = 0;
    do {
        a = a->next;
        b = b->next->next;
        size++;
    } while (a != b);
    return size;
}

相交链表的第一个交点

// a+c +b
// b+c +a
ListNode* func(ListNode* head1, ListNode* head2) {
    auto a = head1;
    auto b = head2;
    while (a != b) {
        a = a ? a->next : head2;
        b = b ? b->next : head1;
    }
    return a;
}

判断是否是回文链表

利用快慢跑得到中间点。同时反转前半部分，然后遍历进行对比

// 判断是否是回文链表 回文链表
bool func(ListNode* head) {
    ListNode* pre = nullptr;
    auto a = head;
    auto b = head;
    while (b && b->next) {
        auto tmp = a;
        a = a->next;
        b = b->next->next;
        // 翻转前半部分
        tmp->next = pre;
        pre = tmp;
    }
    if (b) {
        // 单
        b = pre;
        a = a->next;
        while (a && b) {
            if (a->val != b->val) {
                return 0;
            }
            a = a->next;
            b = b->next;
        }
    } else {
        // 双
        b = pre;
        while (a && b) {
            if (a->val != b->val) {
                return 0;
            }
            a = a->next;
            b = b->next;
        }
    }
    return 1;
}

合并两个排序的链表

ListNode* func(ListNode* head1, ListNode* head2) {
    if (!head1) {
        return head2;
    }
    if (!head2) {
        return head1;
    }
    if (head1->val <= head2->val) {
        head1->next = func(head1->next, head2);
        return head1;
    } else {
        head2->next = func(head1, head2->next);
        return head2;
    }
}