目录

链表中倒数第k个结点

题目

思路

代码

CM11 链表分割

题目

思路

代码 

LCR 027.回文链表

 题目

思路

代码

---

链表中倒数第k个结点

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

题目

输入一个链表，输出该链表中倒数第k个结点。

示例：

输入：1,{1,2,3,4,5}

返回值：{5}

思路

创建两个结构体指针fast和slow指向头节点，先让fast往后遍历，fast通过while循环先走k步后停止，fast和slow同时走，当fast为NULL时，slow所在位置就是倒数第k个。

图示如下👇

代码

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast=pListHead,* slow=pListHead;
    while(fast)
    {         
        fast=fast->next;
        k--;
        if(k<0)
        slow=slow->next;
    }
    if(k>0)
    { 
     return NULL;
    }
    return slow;  
}

CM11 链表分割

链表分割_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

题目

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

示例：

输入：{1,2,3,5,1}

返回值：{1,2,1,3,5}

思路

定义两个哨兵节点，将原链表中节点值大于x和小于x的分别接入两个哨兵节点后，再将大于x的链表去掉哨兵节点后接到小于x的链表后面，要注意的是，记得将新链表最后一个节点置空，不然容易成环。

图示如下👇

代码 

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* ghead,*gtail,*lhead,*ltail;
        ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));
        lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                gtail->next=cur;
                gtail=gtail->next;
            }
            else
            {
                ltail->next=cur;
                ltail=ltail->next;
            }
            cur=cur->next;
        }
        gtail->next=lhead->next;

        ltail->next=NULL;
        struct ListNode* head=ghead->next;
        free(lhead);
        free(ghead);

        return head;
    }
};

LCR 027.回文链表

 LCR 027. 回文链表https://leetcode.cn/problems/aMhZSa/

 题目

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例：

思路

判断链表是否是回文结构，我们可以先找出中间节点mid，从中间节点开始后半段逆置处理，得到新的中间节点rmid，我们可以从整个链表头节点head和rmid开始遍历比较head->val和rmid->val是否相等，若直到rmid->next==NULL时均相等，则为回文结构返回true，反之则直接跳出遍历循环，返回false。

由于代码过长，为了代码更加条理和简洁，找出中间节点和逆置的步骤，我们可以用包装函数的方法实现。

代码

//找中间节点
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

//逆置
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while (cur) {
        //保存下一节点
        struct ListNode* next = cur->next;

        //头插
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

bool isPalindrome(struct ListNode* head){
    struct ListNode* mid=middleNode(head);
    struct ListNode* rmid=reverseList(mid);
    while(head&&rmid)
    {
        if(head->val!=rmid->val)
        {
            return false;
        }
        head=head->next;
        rmid=rmid->next;
    }
    return true;
}