链表刷题(4~8)

目录

反转链表

 返回中间节点

 倒数k个节点

 链表分割

 判断回文

---

反转链表

单链表刷题时我们遇到过一个反转链表，那时我们采用的是头插的方式达到反转的效果，那能不能把指针反过来呢？答案是可以的。

  

这里用三个指针是为了记录后面节点的数据，不然就导致后面的地址缺失，毕竟逻辑结构可不同于物理结构。可以看到结束条件是n2遍历到空就停止。

基于前面刷题的反转链表，现在我们除了头插外有一种新的办法：

力扣

struct ListNode* reverseList(struct ListNode* head)
{
    if(head == NULL)//防止空指针解引用
    {
        return NULL;
    }
    struct ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;
    while(n2)//结束条件
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)//n3为空时保持原样
        {
            n3 = n3->next;
        }
    }
    return n1;
}

 返回中间节点

力扣

查找链表的中间节点有一个思想就是快慢指针：slow指针每走一步，fast指针就走两步。这样做只遍历了一遍链表就找到了中间节点。

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast=head,*slow = head;
    while(fast && fast->next)
    {
        fast = fast ->next->next;
        //fast更新后判断，返回第一个中间结点：if(fast!=NULL)
        slow = slow->next;
    }
    return slow;//快慢指针
 
}

 倒数k个节点

链表中倒数最后k个结点_牛客题霸_牛客网

这道题与前一道题类似，不同的是不知道k为多长，为此，我们可以设置快慢指针，让fast先走k步或k-1步，然后两个指针共同移动。

需要注意不足k步时返回空链表。

truct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {
    struct ListNode* slow,*fast;
    slow = fast = pHead;
    while(k--)//k步
    {
        if(fast == NULL)//不足k步
        {
                return NULL;
        }
        fast = fast->next;
    }
    while(fast)//走k步结束条件
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

 链表分割

 这个题目算是比较难的题，它要求分割后的相对顺序不能改变。这里我们建立两个链表。

一个记录比x小的数据，一个记录相等和比它大的数据，依次进行尾插。最后将两个链表相连。新的链表我们都创建一个哨兵节点(为了避免初始判空和其中一个链表为空的情况进行处理。)

  

这个图我画的比较乱，但思路却很明确。创建哨兵节点，比较，插入，置空，连结，释放，一气呵成。

这里不支持用C实现，我们就先用C++实现。这里的差别在于结构体定义可以不写struct。

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode *greaterhead,*greatertail;
        greaterhead=greatertail=(ListNode *)malloc(sizeof(ListNode));
        ListNode *smallerhead, *smallertail;
        smallertail=smallerhead=(ListNode *)malloc(sizeof(ListNode));
    while(pHead==NULL)
    {
        return NULL;
    }
     ListNode* cur = pHead;
    while(cur)
   { if(cur->val<x)
    {
        smallertail->next = cur;
        smallertail =  smallertail->next;
    }
    if(cur->val>=x)
     {
        greatertail->next = cur;
        greatertail = greatertail->next;
    }
     cur = cur->next;
   }
   smallertail->next = greaterhead->next;//连结
   greatertail->next = NULL;//置空
    ListNode*Next = smallerhead->next;//返回
   free(smallerhead);
   free(greaterhead);
   return Next;
    }
 
};

这里有个小误区就是物理结构与逻辑结构的区别，从图看起来尾插的数据后面没有别的内容，实际上它的next指针还是指向原链表的下一个节点的，虽然是两个新链表和成的一个新链表，但实际上只有哨兵是新开辟的，只是对原链表进行操作，所以要对较大指针的最后一个节点置空。 

判断回文

 正常思路是复制一份链表，然后再此基础上进行反转。但这样的空间复杂度就变成了O(N)。这里介绍一种新奇的方法：根据回文的对称性，反转链表中间及以后的节点。

  

上面两种情况，比较结束条件为一方为空停止比较。

恰好我们实现了查找中间节点和反转链表，所以这里我们可以直接拷贝一份代码。

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL) { //防止空指针解引用
        return NULL;
    }
    struct ListNode* n1, *n2, *n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;
    while (n2) { //结束条件
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3) { //n3为空时保持原样
            n3 = n3->next;
        }
    }
    return n1;
}
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast = head, *slow = head;
    while (fast && fast->next) {
        fast = fast ->next->next;
        //fast更新后判断，返回第一个中间结点：if(fast!=NULL)
        slow = slow->next;
    }
    return slow;//快慢指针
 
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        struct ListNode* mid = middleNode(A);
    struct ListNode* rhead = reverseList(mid);
    while(A && rhead)//一方为空停止
    {
       if( A->val != rhead->val)
       {
        return false;
       }
       A = A->next;
       rhead = rhead->next;
    }
    return true;
    }
};