链表经典题目（上）以及双向链表的增删改查-阿里云开发者社区

力扣链接

自己的效率较低的思路，看看即可

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur=head;
    struct ListNode* tail=head;//追踪倒数第二个节点,快慢指针法
    struct ListNode* Newhead=head;
       if(head==NULL)
       {
          return head;
       }
       if(head->next==NULL)
       {
           return head;
       }
    while(cur->next!=NULL)
    {
        tail=cur;
        cur=cur->next;
    }
    tail->next=NULL;
    Newhead=cur;//记录新节点
    struct ListNode* CunNewhead=Newhead;//不让新节点改变
     while(head->next!=NULL)
     {
      cur=head;
       while(cur->next!=NULL)
       {
          tail=cur;
          cur=cur->next;
       }
       tail->next=NULL;
       CunNewhead->next=cur;
       CunNewhead=cur;
     }
     CunNewhead->next=head;
    return Newhead;
}

经典解法

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

83. 删除排序链表中的重复元素 - 力扣（LeetCode）

struct ListNode* deleteDuplicates(struct ListNode* head){
    if(head==NULL) return head;
//仔细看题是已排序过的
        struct ListNode* slow=head;
        struct ListNode* fast=head->next;
        struct ListNode* tail;
        while(fast)//暴力解法（双指针），
        {//每次迭代时，慢指针跟快指针先比较
         //如果相等，快指针继续走
         //直到快指针走到NULL,因为快指针肯定先走完
           if(slow->val==fast->val)//如果相等，就把值相等的节点释放
           //然后重新链接
           {
               tail=fast;
               fast=fast->next;
               slow->next=fast;
               free(tail);
           }
           else//如果不相等快指针和满指针同时走一步
           {
               slow=slow->next;
               fast=fast->next;
           }
        }
        return head;
}

21. 合并两个有序链表 - 力扣（LeetCode）

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    //含哨兵位的方法
    struct ListNode newnode;
    struct ListNode* head=&newnode;
    head->val=0;
    head->next=NULL;
    struct ListNode* tail=head;
    while(list1!=NULL && list2!=NULL)
    {
      if(list1->val>list2->val)//小的放下来，尾插到哨兵位后面
      {
         tail->next=list2;
         tail=tail->next;
         list2=list2->next;
      }
      else
      {
         tail->next=list1;
         tail=tail->next;
         list1=list1->next;
      }
    }
    if(list1==NULL)//注意情况可能有一边判断完了，另一边还没判断完
    {
       tail->next=list2;
    }
    else if(list2==NULL)
    {
        tail->next=list1;
    }
    return head->next;
}

struct Node* Buynewnode()//申请节点
{
    struct Node* ret =
        (struct Node*)malloc(sizeof(struct Node));
    if (ret == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    ret->val = 0;
    ret->next = NULL;
    ret->random = NULL;
    return ret;
}
struct Node* copyRandomList(struct Node* head) {
    if(head == NULL) return head;//链表可能为空的情况
    struct Node* cur = head;
    struct Node* tail = head;
    struct Node* Copy = NULL;
    struct Node* nnnhead = head;
    while (cur)//每次在给定的链表后面复制一个相同的节点
    {
        Copy = Buynewnode();//每次复制时申请一个节点
        Copy->val = cur->val;//把此时位置的数值复制给新申请的节点
        Copy->next = cur->next;//先让申请的节点链接到旧链表此时位置的
        //下一个节点
        tail = cur->next;
        cur->next = Copy;//让旧的链表此时的位置的节点的下一个节点
        //链接到这个新节点
        cur = tail;
    }
    cur = head;
    tail = NULL;//追着cur->next看看tail是否在copy
    while (cur)//每次要把随机指针指向复制后的跟旧链表相似的节点
    {
        tail = cur->next;
        if (cur->random != NULL)
        {
            cur->next->random = cur->random->next;//因为当前指针的随机
            //指针的下一个节点就是在前面复制过后的节点
        }
        else
        {
            cur->next->random = cur->random;
        }
        cur = cur->next->next;
    }
    tail = head;//保存前一个节点释放节点,
    cur = head->next;
    struct Node* newhead = head->next;
    while (cur && cur->next )//分离复制后的链表，将复制后的
    //链表重新链接
    {
        tail = cur->next;
        cur->next = cur->next->next;
        cur = cur->next;       
    }
    return newhead;
}

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* c1 = headA;
    struct ListNode* c2 = headB;
    int L1 = 0;
    int L2 = 0;
    while (c1)//判断相差的值
    {
        c1 = c1->next;
        ++L1;
    }
    while (c2)//判断相差的值
    {
        c2 = c2->next;
        ++L2;
    }
    int count = abs(L2 - L1);
    //判断长短
    struct ListNode* Short = headA;//假设法
    struct ListNode* Long = headB;
    if (L2 > L1)//判断长短，重新赋值
    {
    }
    else
    {
        Long = headA;
        Short = headB;
    }
    while (count--)//长的先走
    {
        Long = Long->next;
    }
    while (Short != Long)//等短的和长的走到一起时停止,我们相交
    //之后链表后面的节点数量是一样的，而单链表相交只能指向一个地址
    //不能指向两个地址
    {
        Long = Long->next;
        Short = Short->next;
        if (Short == NULL)
        {
            return NULL;
        }
    }
    return Short;
}

带头双向链表

#pragma once
// 带头+双向+链表增删查改实现
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
typedef struct ListNode
{
  LTDataType _data;
  struct ListNode* _next;
  struct ListNode* _prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate();
ListNode* ListCreate()
{
  ListNode* head = (ListNode*)malloc(sizeof(ListNode));
  if (head == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  head->_next=head->_prev = NULL;
  head->_data = -1;//哨兵位
  return head;
}
// 双向链表销毁
void ListDestory(ListNode* pHead);
void ListDestory(ListNode* pHead)
{
    //这里不用判断是否为空的情况，我们的哨兵位不可能为空
   //因为如果为空，我们在创建哨兵位时就已经退出并报错了
  ListNode* cur = pHead->_next;
  ListNode* tail = pHead->_next;
  while (cur)
  {
    tail = cur;
    cur = cur->_next;
    free(tail);
  }
  pHead->_next = NULL;
  pHead->_prev = NULL;
}
// 双向链表打印
void ListPrint(ListNode* pHead);
void ListPrint(ListNode* pHead)
{
  ListNode* cur = pHead->_next;//不要打印哨兵位的数据
  while (cur)
  {
    printf("%d->", cur->_data);
    cur = cur->_next;
  }
  printf("NULL\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);//尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
  ListNode* tail = pHead;//尾插的指针
  ListNode* prev = pHead;//因为要链接前一个，每次遍历时，需要记录上一个节点
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//申请新节点
//链接到尾节点
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->_next = NULL;
  newnode->_prev = NULL;
  newnode->_data = x;//初始化
  while (tail)
  {
    prev = tail;//为什么每次要记录tail经过的上一个节点
        //因为我们这里是双向链表尾插的时候要链接前一个节点
        //相当于我们是在两个节点中插入，
        //左边是正常节点，右边是空，所以根据我的这个思路就用prev
        //并且因为我们没用追随节点的话，tail走到空，
        //当我们在插入的时候，
    tail = tail->_next;
  }
  tail = newnode;
  prev->_next = tail;
  newnode->_prev = prev;  
}
// 双向链表尾删
void ListPopBack(ListNode* pHead);//尾删
void ListPopBack(ListNode* pHead)
{
  ListNode* tail = pHead;
  //ListNode* prev = pHead;//记录前一个节点,给他的next置为空
  while (tail->_next)
  {
    /*prev = tail;*/
    tail = tail->_next;
  }
  if (tail == pHead)//没有结点的情况
  {
    ;
  }
  else
  {
    tail->_prev ->_next = NULL;
    free(tail);
    /*prev->_next = NULL;*/
  }
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);//头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
  ListNode* head = pHead;//哨兵位
  ListNode* cur = pHead->_next;
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//申请新节点
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->_next = NULL;
  newnode->_prev = NULL;
  newnode->_data = x;//初始化
  newnode->_next = head->_next;//将新节点的next指向哨兵位的下一个节点
  newnode->_prev = head;//将新节点的位置的prev指向哨兵位
  head->_next = newnode;//哨兵位的next指向新节点
  if (newnode->_next == NULL)//空节点
    //因为我们如果是在两个节点中插入的话，当第二个节点为空时，
    //我们就不能让他指向前一个节点
  {
    ;
  }
  else
  {
    newnode->_next->_prev = newnode;//第二个节点不为空
  }
}
// 双向链表头删
void ListPopFront(ListNode* pHead);
void ListPopFront(ListNode* pHead)
{
  ListNode* cur = pHead->_next;
  ListNode* tail = cur;
  if (cur)//如果哨兵位后面此时节点为空时，就不要去释放
    //会造成释放空指针
  {
  }
  else if (cur->_next == NULL)//如果节点为1的话我们不用重新链接释放过后的节点
  {
    pHead->_next = cur->_next;//让他们指向空就行
    free(cur);
  }
  else//节点不为1和0的情况
  {
    pHead->_next = cur->_next;
    cur->_next->_prev = pHead;
    free(cur);
  }
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
  ListNode* cur = pHead->_next;
  while (cur)
  {
    if (cur->_data == x)
    {
      return cur;
    }
    cur = cur->_next;
  }
  return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->_next = NULL;
  newnode->_prev = NULL;
  newnode->_data = x;
   //链接前后两个节点,因为pos找不到的话（空节点也包括在内）会我们在前面就会判断并退出，所以我们不需要去判断有木有节点
  newnode->_prev = pos->_prev; //将新节点的prev指向pos位置的前一个节点
  newnode->_next = pos;//将新节点的next指向pos，
  pos->_prev->_next = newnode;//将pos指向的前一个节点的next指向新节点
  pos->_prev = newnode;//将pos的prev指向新节点
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
void ListErase(ListNode* pos)
{
  assert(pos);
  if (pos->_next == NULL)//如果pos的位置是在最后一个的话，我们就不需要去链接
    //新节点，那是为什么呢，我们看第二个条件
  {
    pos->_prev->_next = NULL;
    free(pos);
  }
  else
  {
    pos->_prev->_next = pos->_next;
    pos->_next->_prev = pos->_prev;//如果最后一个节点的nxt指向空，那么
        //pos->_next->_prev就对空指针解引用了
     free(pos);
  }
}

带头双向循环链表

//带头双向循环链表
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
typedef int LTDataType;
typedef struct ListNode
{
  LTDataType _data;
  struct ListNode* _next;
  struct ListNode* _prev;
}ListNode;
// 创建返回链表的头结点.//这个不用改
ListNode* ListCreate();
ListNode* ListCreate()
{
  ListNode* head = (ListNode*)malloc(sizeof(ListNode));
  if (head == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  head->_next = head->_prev = head;
  head->_data = -1;//哨兵位
  return head;
}
// 双向链表销毁
void ListDestory(ListNode* pHead);
void ListDestory(ListNode* pHead)//不用改
{
  ListNode* cur = pHead->_next;
  ListNode* tail = pHead->_next;
  while (cur && cur != pHead)
  {
    tail = cur;
    cur = cur->_next;
    free(tail);
  }
  pHead->_next = pHead;
  pHead->_prev = pHead;
}
// 双向链表打印
void ListPrint(ListNode* pHead);
void ListPrint(ListNode* pHead)//
{
  ListNode* cur = pHead->_next;
  while (cur && cur != pHead)//我们停止条件是cur指向哨兵位时
  {
    printf("%d->", cur->_data);
    cur = cur->_next;
  }
  printf("NULL\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);//尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
    //因为是带头循环的双向链表，我们在初始化时不需要去判断节点是否为空
  ListNode* tail = pHead;//尾插的指针
  ListNode* prev = pHead;//因为要链接前一个，每次遍历时，需要记录上一个节点
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->_next = NULL;
  newnode->_prev = NULL;
  newnode->_data = x;
    //对比双向链表，我们的链表为空时，哨兵位的next和prev都指向的是自己
    //尾插过程
  newnode->_prev = pHead->_prev;
  newnode->_prev->_next = newnode;
  newnode->_next = pHead;
  pHead->_prev = newnode;
}
// 双向循环链表尾删
void ListPopBack(ListNode* pHead);//尾删
void ListPopBack(ListNode* pHead)
{
    //不用判断链表节点是否为空
  pHead->_prev->_prev->_next = pHead;//因为我们的哨兵位的prev
    //指向的时尾节点
  ListNode* cun = pHead->_prev;
  pHead->_prev = pHead->_prev->_prev;
  if (cun != pHead)
  {
    free(cun);
  }
}
// 双向循环链表头插
void ListPushFront(ListNode* pHead, LTDataType x);//头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
  ListNode* head = pHead;//头插的指针
  ListNode* cur = pHead->_next;
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->_next = NULL;
  newnode->_prev = NULL;
  newnode->_data = x;
    //头插的过程
  newnode->_next =pHead->_next;
  pHead->_next->_prev = newnode;
  pHead->_next = newnode;
  newnode->_prev = pHead;
}
// 双向链表头删
void ListPopFront(ListNode* pHead);
void ListPopFront(ListNode* pHead)
{
  assert(pHead);
  assert(pHead->_next != pHead); 
  ListNode* cur = pHead;
    //记住如果不用cur，那我们得理清他的先后顺序
   //因为顺序错了，可能节点就找不到了
  cur = pHead->_next;
  pHead->_next = pHead->_next->_next;
  pHead->_next->_prev = pHead;
  free(cur);
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
  ListNode* cur = pHead->_next;
  while (cur && cur != pHead)
  {
    if (cur->_data == x)
    {
      return cur;
    }
    cur = cur->_next;
  }
  return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
void ListInsert(ListNode* pos, LTDataType x)//不用改
{
  assert(pos);
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->_next = NULL;
  newnode->_prev = NULL;
  newnode->_data = x;
  newnode->_prev = pos->_prev;
  newnode->_next = pos;
  pos->_prev->_next = newnode;
  pos->_prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
void ListErase(ListNode* pos)
{
  assert(pos);
  ListNode* cun = pos;
  pos->_prev->_next = pos->_next;
  pos->_next->_prev = pos->_prev;
  free(cun);
}

链表经典题目（上）以及双向链表的增删改查

带头双向链表

带头双向循环链表

热门文章

最新文章

相关电子书