您的位置:首页 > 游戏 > 游戏 > 数据结构(单链表算法题)

数据结构(单链表算法题)

2024/10/4 1:09:32 来源:https://blog.csdn.net/2401_83968713/article/details/140507410  浏览:    关键词:数据结构(单链表算法题)
  • 1.删除链表中等于给定值 val 的所有节点。 OJ链接

typedef struct ListNode ListNode;struct ListNode {int val;struct ListNode* next;
};struct ListNode* removeElements(struct ListNode* head, int val) {//创建新链表ListNode* newhead, *newtail;newhead = newtail = NULL;//遍历原链表ListNode* pcur = head;while (pcur){if (pcur->val != val)                            //遍历原链表,直到遍历至原链表的值与 val 的结点{if (newhead == NULL)                         //链表为空{newhead = newtail = NULL;}else                                         //链表不为空,将原链表的结点尾插到新链表中{newtail->next = pcur;newtail = newtail->next;}}pcur = pcur->next;}if (newtail)                                         //如果操作完后新的链表不为空,才能 newtail->next = NULL        ;           {newtail->next = NULL;}return newhead;}
  • 思路:创建新链表,将原链表中值不为val的结点尾插到新链表

  • 2.反转一个单链表。 OJ链接

struct ListNode* reverseList(struct ListNode* head) {//处理空链表if (head == NULL){return NULL;}//创建三个指针ListNode* n1, * n2, * n3;n1 = NULL; n2 = head;n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3){n3 = n3->next;}}return n1;
}
  • 思路:创建三个指针,在原链表上就可以修改指针的指向

原链表:       

循环一次后:

以此类推,当 n2 为 NULL 时跳出循环,此时 n1 指向的结点就是链表的新的头结点

(注意:在判断 n3 时要注意他是否已经跳出链表了,因为 n3 是移动的最快的,如果已经跳出链表就不能进行 ->next 操作) 

  • 3.给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。OJ链接

 

struct ListNode* middleNode(struct ListNode* head) {ListNode* slow=head, * fast=head;                 //创建两个指针,快慢指针while (fast && fast->next) {slow = slow->next;                            //慢指针每次走一步,快指针每次走两步fast = fast->next->next;}return slow;                                      //此时慢指针 slow 指向的节点刚好就是中间的结点
}
  • 思路:快慢指针,慢指针每次走一步,快指针每次走两步

当链表长度为奇数时:

 当链表长度为偶数时:

(注意:while 中的(fast && fast->next)顺序不能更改,当 fast 已经为空时,如果改成 

(fast->next && fast),条件会先按顺序执行 fast->next ,从而报错) 

  • 慢指针每次走一步,快指针每次走两步,当快指针走到链表的结尾时,假设链表的长度为 n ,快指针走的路程是慢指针的两倍,此时慢指针走的路程就是 n/2.

  •  4.输入一个链表,输出该链表中倒数第k个结点。 OJ链接

int kthToLast(struct ListNode* head, int k) {ListNode* fast = head,*slow=head;while (k--){fast = fast->next;}while (fast){slow = slow->next;fast = fast->next;}return slow->val;}
  • 思路:创建两个指针,1、先让 fast 向前走K步;
  •                                     2、slow 和 fast 同步前进,fast 到结尾,slow 到目标。

当 fast =NULL

  •  5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJ链接

 

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//处理链表为空if (list1 == NULL)                           //l1为空时,返回l2{return list2;}if (list2 == NULL)                           //l2为空时,返回l1{return list1;}ListNode* newhead, * newtail;               //创建新的链表newhead = newtail = (ListNode*)malloc(sizeof(ListNode));            //创建一个非空链表,减少了判断链表为空和非空情况导致的代码冗余ListNode* l1 = list1;                       //创建两个指针分别指向两个链表的头结点ListNode* l2 = list2;//进行比较尾插while (l1 && l2){if (l1->val < l2->val){newtail->next = l1;newtail = newtail->next;l1 = l1->next;}else{newtail->next = l2;newtail = newtail->next;l2 = l2->next;}}if (l1)                                     //跳出循环只用两种情况:要么 l1 为空(l2 肯定不为空);要么 l2 为空(l1 肯定不为空){newtail->next = l1;}if (l2){newtail->next = l2;}ListNode* ret = newhead->next;free(newhead);newhead = NULL;return ret;
}
  •  思路:创建新链表,遍历原链表,谁小就尾插到新链表中

  • 6.编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前 。OJ链接

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code hereListNode* lesshead,*lesstail;lesshead=lesstail=(ListNode*)malloc(sizeof(ListNode));   //大链表ListNode* greathead,*greattail;greathead=greattail=(ListNode*)malloc(sizeof(ListNode)); //小链表ListNode* pcur =pHead;                                //遍历链表while(pcur){if(pcur->val<x)                          //当原链表结点的值小于 x,尾插到小链表 {lesstail->next=pcur;lesstail=lesstail->next;}else                                    //当原链表结点的值大于 x,尾插到大链表 {greattail->next=pcur;greattail=greattail->next;}pcur=pcur->next;}greattail->next=NULL;                       //将大链表的尾结点的 next 指针置为NULLlesstail->next=greathead->next;              // 大小链表首尾相连ListNode* ret= lesshead->next;free(lesshead);free(greathead);lesshead=greathead=NULL;return ret;}
};
  •  思路:创建大链表、小链表,将小于 x 值的结点尾插到对应的链表中,最后小链表的尾与大链表的头相连。
  • (注意:不能忘了最后将大链表的 next 指针指向= NULL)

  • 7.链表的回文结构。OJ链接 

bool chkPalindrome(ListNode* A) {// write code hereListNode* mid=middleNode(A);           //找出原链表的中间结点ListNode*right=reverseList(mid);      //以次中间结点为头结点反转后面的链表ListNode*left=A;                    //从原链表和反链表比较结点的值while(right){if(left->val!=right->val){return false;}left=left->next;right=right->next;}return true;}
  • 思路:1、找出链表的中间结点
  •            2、将中间结点之后的链表进行反转
  •            3、从原链表和反链表比较结点的值

未完待续~~

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com