定義ListNode節(jié)點(diǎn)結(jié)構(gòu)體
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.鏈表逆序
一只鏈表頭節(jié)點(diǎn)庇忌，指針head，將鏈表逆序。（不可申請(qǐng)額外空間）
鏈表數(shù)據(jù)結(jié)構(gòu)
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.構(gòu)造5個(gè)節(jié)點(diǎn)a,b,c,d,e,并對(duì)它們進(jìn)行初始化；
2.將a,b,c,d,e,5個(gè)節(jié)點(diǎn)連接在一起
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.移動(dòng)head與new_head
class Solution{
public :
ListNode *reverseList(ListNode * head){
ListNode *new_head =NULL;//指向新鏈表頭節(jié)點(diǎn)的指針
while(head){
ListNode * next = head->next;//備份head->next
head->next = new_head; //更新head->next
new_head = head_next; //移動(dòng)new_head
head = next;//遍歷鏈表
}
return new_head;//返回新鏈表頭節(jié)點(diǎn)
}
}
2款筑、頭插法
設(shè)置一個(gè)臨時(shí)頭節(jié)點(diǎn)temp_head,利用head指針遍歷鏈表，每遍歷一個(gè)節(jié)點(diǎn)即將該節(jié)點(diǎn)插入到temp_head后
1.備份next = head->next;
2.修改head->next
3.temp_head.next
4.移動(dòng)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;
}
}
