題目：

206. 反轉(zhuǎn)鏈表

難度簡(jiǎn)單3050

給你單鏈表的頭節(jié)點(diǎn)?head?，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

?

示例 1：

輸入：head = [1,2,3,4,5]輸出：[5,4,3,2,1]

示例 2：

輸入：head = [1,2]輸出：[2,1]

示例 3：

輸入：head = []輸出：[]

?

提示：

• 鏈表中節(jié)點(diǎn)的數(shù)目范圍是?[0, 5000]

• -5000 <= Node.val <= 5000

?

進(jìn)階：鏈表可以選用迭代或遞歸方式完成反轉(zhuǎn)。你能否用兩種方法解決這道題？

第一種對(duì)法：

/**

?*?Definition?for?singly-linked?list.

?*?struct?ListNode?{

?*?????int?val;

?*?????struct?ListNode?*next;

?*?};

?*/

struct?ListNode*?reverse(struct?ListNode*?cur,struct?ListNode*?pre){

????if(cur==NULL)return?pre;

????struct?ListNode?*tmp?=?cur->next;

????cur->next?=?pre;

????return?reverse(tmp,cur);

}

struct?ListNode*?reverseList(struct?ListNode*?head){

????return?reverse(head,NULL);

}

遞歸寫法，最后記得return

第二種對(duì)法：

/**

?*?Definition?for?singly-linked?list.

?*?struct?ListNode?{

?*?????int?val;

?*?????struct?ListNode?*next;

?*?};

?*/

struct?ListNode*?reverseList(struct?ListNode*?head){

????struct?ListNode?*tmp;

????struct?ListNode?*cur;

????struct?ListNode?*pre;

????cur?=?head,pre=?NULL;

????while(cur){

????????tmp?=?cur->next;

????????cur->next?=?pre;

????????pre?=?cur;

????????cur?=?tmp;

????}

????return?pre;

}

迭代寫法，先把cur的next保存下來，避免斷鏈

第三種對(duì)法：

struct?ListNode*?reverseList(struct?ListNode*?head){

????struct?ListNode?*p?=?(struct?ListNode*)malloc(sizeof(struct?ListNode));

????p->next?=?NULL;

????struct?ListNode?*cur?=?head;

????while(head){

????????cur?=?head->next;

????????head->next?=?p->next;

????????p->next?=?head;

????????head?=?cur;

????}

????return?p->next;

}

頭插法；