leetcode206翻转链表
题目描述:
给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2] 输出:[2,1]
示例 3:
输入:head = [] 输出:[]
算法思想:
创建一个空链表头指针,将原给链表的节点依次遍历并采用头插法插入新创建的空链表头指针后完成翻转。
真正的草图哈哈哈!希望你能懂。没有官方的双指针快,但我觉得好理解一些,官方的双指针跟着画一遍图就能理解了。
算法实现:
ListNode* reverseList(ListNode* head) {
//创建新的链——带头指针的
ListNode *newList=new ListNode();
while(head){
//剥离当前指针指向的节点
ListNode *node=head;
head=head->next;
node->next=nullptr;
//第一个节点单独处理
if(newList->next==nullptr) newList->next=node;
//头插法插入
else{
node->next=newList->next;
newList->next=node;
}
}
//返回反转后的链表。注意这时候要把新链无意义的头节点去掉
return newList->next;
}
leetcode24——两两交换链表中的节点
题目描述:
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4] 输出:[2,1,4,3]
示例 2:
输入:head = [] 输出:[]
示例 3:
输入:head = [1] 输出:[1]
算法思想:
草图将就着看,哈哈哈。官解很牛有时间在钻研
算法实现:
ListNode* swapPairs(ListNode* head) {
ListNode* cur=head;
//若有交换返回node,因为在第一次交换后node变成了头
ListNode* node=new ListNode();
//flag标志着有没有进行交换
int flag=0;
//链表长度大于等于2才进行交换
if(cur!=nullptr && cur->next!=nullptr){
//第一种情况头节点的处理
node=cur->next;
cur->next=node->next;
node->next=cur;
flag=1;
//其余节点的处理,有三个指针发生变化长度肯定要大于三
while(cur && cur->next && cur->next->next){
//动动小手画画图你随便理解
ListNode* node1=cur->next;
ListNode* node2=node1->next;
cur->next=node1->next;
node1->next=node2->next;
node2->next=node1;
cur=node1;
}
}
if(flag) return node;
else return head;
}
标签:node,head,ListNode,cur,next,链表,攻克
From: https://blog.csdn.net/ch_ah/article/details/140530143