题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1: 输入:head = [1, 2, 3, 4, 5] 输出:[5, 4, 3, 2, 1]
示例 2: 输入:head = [1, 2] 输出:[2, 1]
示例 3: 输入:head = [] 输出:[]
这个思路的图如下:
代码:
struct ListNode* reverseList(struct ListNode* head)
{
//空链表返回空
if (head == NULL)
{
return NULL;
}
//定义两个结构体指针newhead,cur
struct ListNode* newhead = head, * cur;
//new找到链表的最后一个结点,最后返回这个结点
while (newhead->next)
{
newhead = newhead->next;
}
//将尾部赋给cur
cur = newhead;
//head是原链表的头结点,所以反转之后head的next应该是NULL,若head的next不为空循环继续
while (head->next)
{
//每次进来都定义一个结构体指针newtail,从头开始找
//直到newtail的next为cur停下
struct ListNode* newtail = head;
while (newtail->next != cur)
{
newtail = newtail->next;
}
//将cur的next链接上一个结点
cur->next = newtail;
//如果cur的前一个结点是head,将head的next指向空,即为尾部
if (cur->next == head)
{
head->next = NULL;
}
//每次循环后更新cur
cur = newtail;
}
return newhead;
}
这个思路的图如下,prev记录上一个结点,最后也是返回prev,next是为记录下一个结点;
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* prev = NULL, * curr = head;
//当curr不为空循环继续
while (curr)
{
//next记录下一个结点
//prev记录上一个结点
struct ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
题目:给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。
示例 1: 输入:head = [1, 2, 3, 4, 5] 输出:[3, 4, 5] 解释:链表只有一个中间结点,值为 3 。
示例 2: 输入:head = [1, 2, 3, 4, 5, 6] 输出:[4, 5, 6] 解释:该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。
这个思路就是统计链表的长度,然后将长度除以2取商,再从头开始走取商的步数即可;
struct ListNode* middleNode(struct ListNode* head)
{
//count记录链表的长度
//curr用来返回
int count = 0;
struct ListNode* curr = head;
//找空指针,统计链表长度
while (curr)
{
curr = curr->next;
count++;
}
//让curr返回头部
curr = head;
//中间结点需要走的步长
//用循环将curr往后走就行了
int mid = count / 2;
while (mid)
{
curr = curr->next;
mid--;
}
return curr;
}
这个思路的图如下:
初始化好的情况:(长度为奇数)
最后的结果:
长度为偶数:
结果图:
代码和注释:
struct ListNode* middleNode(struct ListNode* head)
{
//两个指针都从头开始
struct ListNode* slow = head, * fast = head;
//长度为偶数时fast为空,为奇数时fast->next为空
while (fast && fast->next)
{
//slow每次走一步
//fast每次走两步
slow = slow->next;
fast = fast->next->next;
}
//最后slow就是要返回的指针
return slow;
}