题目一 反转链表
解法一
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/UHnkqh
还是一样 我们画图来分析下
代码表示如下
struct ListNode* reverseList(struct ListNode* head) { if(head==NULL) { return head; } struct ListNode* prev =NULL; struct ListNode* pos = head; struct ListNode* next = head; prev = pos; pos = pos->next; prev->next = NULL; while(pos) { next = pos; pos = pos->next; next->next =prev; prev = next; } return next; }
这就是解法一 思路很简单 也可以很顺畅的运行
解法二
还是先画图给大家看看
代码表示如下
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newhead = NULL; struct ListNode* next =NULL; struct ListNode* pos =NULL; pos = head; next = head; while(next) { next = next->next; pos->next = newhead; newhead = pos; pos = next; } return newhead; }
题目二 链表的中间节点
这道题目就是一个经典的快慢指针问题
我们可以设置两个指针
慢指针先走 每次走一格
快指针再走 每次走两格
当快指针指向最后一个节点或者是空指针的时候直接return slow就可以
代码表示如下
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while ((fast!=NULL)&&(fast->next!=NULL)) { slow=slow->next; fast=fast->next->next; } return slow; }
很简单 大家领悟一下思路就可以
题目三 链表的倒数第K个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
还是跟上面的题 思路一样
还是一个快慢指针的问题
这里要求倒数k个位置
只需要让fast先走k步就可以
放fast走到NULL的时候return solw的值
当然这里要注意 如果说fast走到了NULL k还没有归零
那么这个时候就要返回空指针了
代码表示如下
struct ListNode* getKthFromEnd(struct ListNode* head, int k) { struct ListNode* slow =head; struct ListNode* fast = head; while(fast && k--) { fast =fast->next; } if((fast==NULL) && (k>0)) { return fast; } while(fast) { fast = fast->next; slow = slow->next; } return slow; }
题目四 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
画图这样子就很好理解
当然这里要考虑两个特殊情况
如果说像这样子 l2数组为空 那么只需要将head = l1
返回head就可以
反之亦然
代码表示如下
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* head = NULL; struct ListNode* tail = NULL; if(list1==NULL) { head = list2; return head; } if(list2==NULL) { head =list1; return head; } while(list1 && list2) { if((list1->val)<(list2->val)) { if(head == NULL) { head = tail =list1; } else { tail ->next = list1; tail=tail->next; } list1=list1->next; } else { if(head == NULL) { head = tail =list2; } else { tail ->next = list2; tail=tail->next; } list2=list2->next; } } if(list1) { tail->next=list1; } else { tail->next=list2; } return head; }
