链表OJ题+牛客题

目录

206.反转链表

876.链表的中间节点

链表中倒数第k个节点

CM11链表分割

OR36 链表的回文

---

206.反转链表

给你单链表的头节点head,请你反转链表，并返回反转后的链表。

 实现如下结果：

        

 思路：

取链表中的节点头插：

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
 
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *cur=head;
struct ListNode *plist=NULL;
while(cur)
{
   struct ListNode *next=cur->next;
    
    cur->next=plist;//cur->next指向plist的地址
    
    plist=cur;          //plist 指向cur的地址，刚上面的一行代码和这一行代码使得链表的空间相连
    cur =next; 
}
return plist;
}/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
 
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *cur=head;
struct ListNode *plist=NULL;     //作为新的头节点
while(cur)
{
   struct ListNode *next=cur->next;     //记住cur的下一个节点
    
    cur->next=plist;//      头插
    
    plist=cur;          //换头
    cur =next;          //将原来cur->next节点的地址赋给cur
}
return plist;
}

876.链表的中间节点

给定一个头节点为head的非空单链表，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。要求只能遍历一遍

思路：用快慢指针找到中间节点，定义两个结构体变量指针slow,fast。

slow每次走一步，fast每次走两步。当fast->next为空的时候,则链表长度为奇数,那么slow就是中间节点；当fast为空时，链表的长度为偶数，那么中间节点有两个，则返回第二个中间节点。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
 
struct ListNode* middleNode(struct ListNode* head){
struct ListNode *fast,*slow;
slow=fast=head;
while(fast&&fast->next)
{
    slow=slow->next;
    fast=fast->next->next;
}
return slow;
}

链表中倒数第k个节点

输入一个链表，输出该链表中第k个节点

思路：定义结构体指针变量slow,fast,让fast先走k部,然后它们都各自每次向后走一步，当fast为空的时候，返回slow,此时slow就为链表中第k个节点。也可以让fast先走k-1步，当fast->next为空的时候，slow就是链表中第k个节点。

在这里需要注意的就是要注意k的值是否大于链表的长度，如果大于则返回NULL.

 代码：

struct ListNode*FindKthToTail(struct ListNode*pListHead,int k)
{
    struct ListNode*fast,slow;
    fast=slow=pListHead;
    while(k--)//让fast先走k步
    {
        //链表可能没有k步长
        if(fast==NULL)
        {
        return NULL;
        }
    fast=fast->next;
    }
 
    while(fast)//当fast为空
    {
    fast=fast->next;
    slow=slow->next;
    }
return slow;
}

CM11链表分割

描述：

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

思路：

这道题用带哨兵位的链表求解，将所有小于x的节点尾插到第一个哨兵位节点后面；其余的尾插到第二个带哨兵位节点后面；最后将两个链表链接，返回第一个哨兵位节点后一个节点。

这里需要注意的是，在最后尾插结束时记得将第二个链表的尾节点的下一个节点置空（即上图的greaterTail的下一个节点置空），因为尾插结束，greaterTail->next还指向链表中的其他节点，如果不置空，会形成环。

 

代码： 

class Partition
{
    public:
ListNode *Partition(ListNode*pHead,int x)
{
    struct ListNode*lessHead,*lessTail;
    struct ListNode*greaterHead,*greaterTail;
    lessHead=lessTail=(struct ListNode*)malloc(sizeof(structListNode));
    greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
    lessTail->next=greaterTail->next=NULL;
 
struct ListNode*cur=pHead;
while(cur)
{
    if(cur->val
    {
        lessTail->next=cur;
        lessTail=lessTail->next;
    }
    else
    {
        greaterTail->next=cur;
        greterTail=greaterTail->next;
    }
    cur=cur->next;
}
lessTail->next=greaterHead->next;
greaterTail->next=NULL;
 
pHead=lessHead->next;
free(lessHead);
free(greaterHead);
 
return pHead;
}
}

OR36 链表的回文

描述：

对于一个链表，请设计时间复杂度为O(n),空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900.

 思路：将链表的后半部分的节点逆置，再将前半部分的值和后半部分的值相比。因为额外的空间复杂度为O(1)，所以不能整体逆置，整体逆置要重新开辟一个和原来一样长的链表空间。所以这里将后半部分的节点逆置之后就可以比较了。

代码：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    struct ListNode* middle(struct ListNode* phead)  //返回中间值
    {
        struct ListNode*fast,*slow;
        fast=slow=phead;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
 
 
struct ListNode*reverse(struct ListNode*phead)
{
    struct ListNode*cur=phead;
    struct ListNode*rehead=NULL;
    while(cur)
    {
        struct ListNode*next=cur->next;
        //头插
        cur->next=rehead;
        rehead=cur;
 
 
        cur=next;
    }
    return rehead;
}
 
 
    bool chkPalindrome(ListNode* A)
     {
         struct ListNode*mid=middle(A);
        struct ListNode*rehead=reverse(mid);
        while(A && rehead)
        {
            if(A->val!=rehead->val)
            return false;
            A=A->next;
            rehead=rehead->next;
        }
 
 
        return true;
        // write code here
    }
};