链表逆序
定义ListNode节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x),next(NULL)
}例题： 链表链接
int main(){
ListNode a(10);
ListNode b(20);
ListNode c(30);
ListNode d(40);
ListNode e(50);
a.next = & b;
b.next = & c;
c.next = & d;
d.next = & e;
ListNode *head = & a;
while(head){
print("%d %p %P\n,head->val, head,head->next");
head = head->next
}
return 0;
}LeetCode 206. Reverse Linked List
Eg1.链表逆序
一只链表头节点，指针head，将链表逆序。（不可申请额外空间）
链表数据结构
struct ListNode{
int val;
ListNode *next;
ListNode(int x) : val(x),next(NULL){}
};打印head指针指向的链表
void print_list(ListNode * head,const char *List_name){
printf("%S :",List_name);
if(!head){
printf("NULL\n");
return;
}
while(head){
printf("%d",head->val);
head = head->next;
}
printf("\n");
}1.构造5个节点a,b,c,d,e,并对它们进行初始化； 2.将a,b,c,d,e,5个节点连接在一起
int main(){
ListNode a(1);
ListNode b(2);
ListNode c(3);
ListNode d(4);
ListNode e(5);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
ListNode *head =&a;
ListNode *new_head = NULL;
LIstNode *next = NULL;
print_list(head,"old");
print_list(new_head,"new");
return 0;
}
1、就地逆置法
1.备份head->next 2.修改head->next 3.移动head与new_head
class Solution{
public :
ListNode *reverseList(ListNode * head){
ListNode *new_head =NULL;//指向新链表头节点的指针
while(head){
ListNode * next = head->next;//备份head->next
head->next = new_head; //更新head->next
new_head = head_next; //移动new_head
head = next;//遍历链表
}
return new_head;//返回新链表头节点
}
}2、头插法
设置一个临时头节点temp_head,利用head指针遍历链表，每遍历一个节点即将该节点插入到temp_head后
1.备份next = head->next; 2.修改head->next 3.temp_head.next 4.移动head
class Solution{
public:
ListNode * reverseList(ListNode * head){
ListNode temp_head(0);
while(head){
ListNode *next = head->next;
head->next = temp_head.next;
temp_head.next = head;
head =next;
}
return temp_head.next;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.03.05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录