LeetCode链表OJ题

目录

206. 反转链表 - 力扣（LeetCode）

​编辑

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

​编辑

链表分割_牛客题霸_牛客网 (nowcoder.com)

 《27. 移除元素 - 力扣（LeetCode）》

160. 相交链表 - 力扣（LeetCode）

88. 合并两个有序数组 - 力扣（LeetCode）

876. 链表的中间结点 - 力扣（LeetCode）

链表的回文结构__牛客网 (nowcoder.com)

141. 环形链表 - 力扣（LeetCode）

 142. 环形链表 II - 力扣（LeetCode）

第一种方法：

代码：

 
struct ListNode* reverseList(struct ListNode* head){
if(head==NULL)
{
    return NULL;
}
struct ListNode* tail=NULL;
struct ListNode* src=head;
struct ListNode* dst=src->next;
 
while(src)
{ 
    src->next=tail;
 tail=src; 
src=dst;
    if(dst)
dst=dst->next;
   
 
 
}
return tail;
}

思路：

 首先把tail放到NULL的位置，然后把src的next指向tail，然后把tail给给src，把src给给dst

然后再重复上一个步骤就可以实现第二个节点指向第一个节点 

然后重复即可。 

报错：

 修改：假如只有两个节点：

 那dst=dst->next要把dst跳到哪里呢？

所以我们要判断一下dst是否为空:

 报错：

 解析：这个就是head为空的问题，head如果为空，我们怎么连下一个节点呢，，没必要连了，所以判断一下，如果head为空，那么就什么都不返回。

第二种方法：头插法

思路是：创建一个cur，cur在head的位置上（cur=head），然后再创建一个next变量，这个变量在cur的下一个节点上。(next=cur->next）。再创建一个空节点，然后让rhead这个变量等于NULL。（rhea=NULL;）

 然后我们把cur跟NULL连起来，（cur->next=rhead）再把rhead给cur。(cur=rhead)

 然后再把cur给给next。(next=cur)；再让next跳到下一个节点上

 然后再重复上个步骤，再让cur指向rhead:

 依次类推，最终会实现逆转：

 代码：

struct ListNode* reverseList(struct ListNode* head){
if(head==NULL)
{
  return NULL;
}
 
struct ListNode* rhead=NULL;
struct ListNode* cur=head;
 
 
while(cur)
{
 
  struct ListNode* next=cur->next;
 
  cur->next=rhead;
rhead=cur;
cur=next;
 
}
 
 
return rhead;
 
}

要注意的两点：

第一点：传值

while(head)
{
 
  struct ListNode* next=cur->next;
 
  cur->next=rhead;
rhead=cur;
cur=next;
 
}

 像这里就会报错，因为我们传head进去，判断head是否会空，我们知道head是但是当第一次运算完之后这个节点就指向空了，

 第二次判断就直接退出循环了，所以我们要传cur。

第二点：返回值：

return cur

这里也会报错，因为我们最后要返回的是一个头结点，而cur最后会到最后那个节点 

 所以我们应该传rhead ,它才是头结点。

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

思路：快慢指针

slow,fast两个指针

让快指针先走k个节点，然后停下再让，slow指针开始走，然后fast指针再走，两个分别一人走一下，直到fast指针走完结束，此刻slow指针就是我们要找的倒数第k个节点

代码：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
struct ListNode* fast= pListHead,* slow=pListHead;
  // write code here
while(k--)
{
  
fast=fast->next;
}
while(fast)
{ 
  slow=slow->next;
 fast=fast->next;
  
}
 
 
return slow;
}

报错：

根据下面的三个图我们可以看出问题所在： 

 从第三个案列开始，K都超过了链表的长度，然后预期输出里面都返回的空值，而我们的实际输出根本就输出不出来，因为我们没有设置如果k>链表长度则retuen NULL;这个条件。

 看第三个案列：

6{1，2,3,4,5}

 我们的链表总共就5个节点，fast走到第五个节点再往下走第六个节点就是NULL了

 所以我们只需要设置：

if(fast==NULL)
return NULL;

可运行的 代码：

链表分割_牛客题霸_牛客网 (nowcoder.com)

思路：尾插法

比如有一串数字：

 我们把小于9的放一个链表，大于9的放一个链表：

 因为是尾插，所以顺序不会变，然后我们把这两个链表链接起来。

 代码：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* lesshead,*lesstail;
        struct ListNode* greathead,*greattail;
        lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
           greathead=greattail=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur=pHead;
if(pHead==NULL)
{
  return NULL;
}
           while(cur)
           {
            if(cur->val<x)
            {
              lesstail->next=cur;
              lesstail=lesstail->next;
            }
            else 
            {
           greattail->next=cur;
           greattail=greattail->next;
            }
            cur=cur->next;
 
            }
            lesstail->next=greathead->next;
            
            free(lesshead);
            free(greathead);
return pHead;
           
 
    }
};

 报错：

 我们自己输入一个测试用例然后运行，输出结果为空，就是输出不出来。

 然后我们再看报错提示：就是数组越界，堆栈溢出。

其实就是没有释放哨兵位：

我们应该把创建的

 struct ListNode* lesshead,*lesstail;
        struct ListNode* greathead,*greattail;

 释放掉。

虽然我们已经用free释放了，

  free(lesshead);
            free(greathead);

但是我们应该把哨兵位归为，把lesshead回到开头的位置。什么意思，就是把lesshead放到head前面，再释放它，对整个链表不影响。

head=lesshead->next;
  free(lesshead);
            free(greathead);

 去掉lesshead不影响链表 

 改完之后还有个报错：

 极端的错误：

要么全是小于x的

要么全是大于x的

要么有大有小的

我们自测输入，输入全是小于x的，正常运行

 输入全大于x的，正常运行

 输入有大有小的，

 报错了，根据实际输出可以看出来陷入了死循环。也就是

这个样子，我们的 greattail节点本来应该指向NULL，但是却指向了lesstail，就造成了死循环。

正常的应该是这个样子：

所以我们只需要把gretail的next指向NULL就可以了

greattail->next=NULL;

 通过代码：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* lesshead,*lesstail;
        struct ListNode* greathead,*greattail;
        lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
           greathead=greattail=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur=pHead;
if(pHead==NULL)
{
  return NULL;
}
           while(cur)
           {
            if(cur->val<x)
            {
              lesstail->next=cur;
              lesstail=lesstail->next;
            }
            else 
            {
           greattail->next=cur;
           greattail=greattail->next;
            }
            cur=cur->next;
 
            }
            lesstail->next=greathead->next;
            pHead=lesshead->next;
            greattail->next=NULL;
            free(lesshead);
            free(greathead);
return pHead;
    }
};

 《27. 移除元素 - 力扣（LeetCode）》

这道题怎么解：

用一个src和一个dec

​都从第一个数开始跑，但是src要先跑，并且dec不可以超过src。

接着判断src是否等于val的值,如果等于val，那么就只有src++，dec不动。如果src不等于val，那么src就赋值给dec，把dec的值覆盖掉，这样dec就只肯定不是val的值了，就可以保证前面一定不是val的值。然后再把src和dec都++，继续重复。

刚开始:

​

 ​

​

 ​

 只考虑前半段，因为前半段是有效的后半段是无效的，​

 前面的{2,2}就是我们要的结果​

 代码：

int removeElement(int* nums, int numsSize, int val){
int DEC=0;
int src=0;
while(src<numsSize)
{
   if(nums[src]!=val)
   {
      nums[DEC++]=nums[src++];
   }
   else
   {
      src++;
   }
}
return DEC;
}

160. 相交链表 - 力扣（LeetCode）

1.判断两个链表的尾节点是否相等，相等则相交。

但是时间复杂度太大，更简单一点的，我们向前再挪一点，判断c1是否相等不是可以少计算一点吗，时间复杂度也会小点。

那应该如何去判断呢？

 让src去遍历B链表的每个节点从B1直到c3节点 ，看是否与a1相等，如果不相等，src++，到a2头上，再去遍历B链表，直到src到c1头上时去遍历B链表，也遍历到了B链表的c1节点，发现相等，那就相交。

但是这个时间复杂度：src一次要遍历n个节点，O（N）。要遍历N遍，那就是O(N*N)

有个时间复杂度少一点的：谁长谁先走一步。

然后同时走，每走一个就对比一下节点是否为同一个节点，直到走到相同节点，那就相交。

 这个时间复杂度就是O(N).

这个代码报错了，为什么？

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
 
    struct ListNode * longLlist=headA;
    struct ListNode * shortLlist=headB;
   
 
    
    if(shortLlist>longLlist)
    {
     
       shortLlist=shortLlist->next;
    } 
    while(longLlist->next&&shortLlist->next){
    if(shortLlist->next==longLlist->next)
    {
        return longLlist;
    }
    }
    return NULL;
    
}

第一，这里只定义了longLlist，shortLlist.但是没有实际意义，因为根据就没有去计算链表的长度。

我们应该让src一直走，每走一个len++，把A链表的长度计算出来，

B链表同理。

第2，不是谁长谁先走一步，而是谁长谁先长的步数，比如说下图：

 这让dst先走一步，再让src和dst同步走，两个也走不到一个节点上。只能让dst先走abs(dst-src）步，再让两者同步走。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
 
    struct ListNode * src=headA;
    struct ListNode * dst=headB;
 
    int lenA=1,lenB=1,len=1;
   while(src->next)
   {
       src=src->next;
       lenA++;
   }
 while(dst->next)
   {
      dst=dst->next;
       lenB++;
   }
   if(src!=dst)
   {
       return NULL;
   }
struct ListNode * longLlist= headA;
  struct ListNode * shortLlist=headB;
  int gap=0;
gap=abs(lenA-lenB);
 
 
    if(lenA<lenB)
    {
longLlist= headB;
  shortLlist=headA;
    } 
 
 
    while(gap--)
    {
            longLlist=longLlist->next;
    }
    
    while(longLlist!=shortLlist)
    {
       longLlist= longLlist->next;
       shortLlist=shortLlist->next;
    }
    
    
        return longLlist;
    
 
    
   
    
}

88. 合并两个有序数组 - 力扣（LeetCode）

思路：

这道题的意思是，A链表开辟m+n个空间，但是元素只有m个，B链表开辟n个空间，元素有n个

 然后按照升序排列把B链表合并过去，我们要的最终效果是这个样子：

 思路：

 1.设end1=m；

end2=n-1

i=m+n-1;

-1的原因是下标从0开始

 2.进行比较。

if     num1[end1]<nums2[end2]

这种情况的话就把nums2[end2]赋值给nums1[end2]

比如nums2[end2]=6,nums1[end1]=3,就把nums2[end2]复制给nums1[i]；

 然后end2--，i--, end2和end1对比，end2大，执行nums1[i--]=nums2[end2--];

 end2和end1对比，end1大，执行  nums1[i--]=nums1[end1--];

然后执行end1--，i--，end2和end1对比，一样大，执行  nums1[i--]=nums2[end2--];
}

end2<0就结束了。

}

还有一种情况就是end1先走完。

 这种情况就是end1<0了，但是end2还大于0，但是还没完成合并，所以这里要单独写

while(end2>0)

就把nums2[end2]赋值给nums1[i]的位置

 结束

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
 
int end1=m-1;
int end2=n-1;
int i=m+n-1;
while(end1>=0&&end2>=0)
{
    if(nums1[end1]>nums2[end2])
{
    nums1[i--]=nums1[end1--];
}
else
{
     nums1[i--]=nums2[end2--];
}
 
}
while(end2>=0)
{
    nums1[i--]=nums2[end2--];
 
}
}

876. 链表的中间结点 - 力扣（LeetCode）

思路：快慢指针

当链表为奇数链表时：

fast一次走两步，slow一次走一步，fast走完（fast=NULL），slow刚好走到中间 

当链表为偶数链表时，fast走超了一节点(fast->next->next=NULL)，slow刚好走到中间：

struct ListNode* middleNode(struct ListNode* head){
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast&&fast->next)//fast!=NULL是奇数链表， fast->next不为空是偶数链表
{
    fast=fast->next->next;
    slow=slow->next;
}
return slow;
}

链表的回文结构__牛客网 (nowcoder.com)

思路：找到链表中间节点，876. 链表的中间结点 - 力扣（LeetCode）

从中间节点开始逆置206. 反转链表 - 力扣（LeetCode）

//反转函数
struct ListNode* middleNode(struct ListNode* head) {
  struct ListNode* slow = head;
  struct ListNode* fast = head;
  while (fast && fast->next) {
    fast = fast->next->next;
    slow = slow->next;
  }
  return slow;
}
 
//逆置函数
struct ListNode* reverseList(struct ListNode* head) {
  if (head == NULL) {
    return NULL;
  }
  struct ListNode* tail = NULL;
  struct ListNode* src = head;
  struct ListNode* dst = src->next;
 
  while (src) {
    src->next = tail;
    tail = src;
    src = dst;
    if (dst)
      dst = dst->next;
  }
  return tail;
}
 
 
 
 
 
//判断函数
class PalindromeList {
 public:
  bool chkPalindrome(ListNode* A) {
    // write code here
 
    ListNode* Pops=middleNode(A);
     ListNode* rmid=reverseList(Pops) ;
   while(rmid)
   {
    if(rmid->val!=A->val)//判断反转逆置完的第一个数的值是否相同
    {
      return false;
    }
    else//相同则判断下个节点的值是否相同
    {
      A=A->next;  
      rmid=rmid->next;
    }
   
   }
    return true;
  }
};

141. 环形链表 - 力扣（LeetCode）

首先，怎么判断是不是环形链表

1.我们可以通过快慢指针的方式，如果fast走到空就不是环形

2.如果fast->next-走到空就不是环形

上面这两种情况都不是环形，不是环形就返回false

 3.否则就是环形，是环形救直接返回true值吗，并不是，因为还要判断一下是否一个节点的next会回到前面的节点

快指针一次走两步，慢指针一次走一步，进入环里后，两个指针早晚会相遇。

这是因为假设fast和slow的距离为N（fast去追slow）

fast每次走两步，slow一次走1步，每同时走一次，fast和slow之间距离就缩小一步,也就是N-1.

再走一次就是N-2，最后会走到4,3,2,1,0,走到0的时候fast和slow就相遇了。

如果相遇，就返回true值

如果fast一次走3步，slow一次走1步，会相遇吗？

fast一次走3步，slow一次走一步，距离就缩小2步，N-2，第二次是N -4，最后会走成3,1，-1。

走到-1就错过了。

 如果错过了，fast和slow会继续走，fast会再次去追slow追几圈能追上不知道，能不能追上要看N-1减到最后是0还是-1，如果是0就追上了，如果是-1那就是没追上。

bool hasCycle(struct ListNode *head) {
    struct ListNode*  slow=head;
    struct ListNode* fast=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        
     
     if(slow==fast)
     {return true;
       
     }
     }
     return false;
}

 142. 环形链表 II - 力扣（LeetCode）