背景
image.png
解決方案
第一種解決方案 直接反轉(zhuǎn)
//這種方式是錯誤的方法蜓竹。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
//錯誤的方法亭珍，可能會導致循環(huán)鏈表。
while(head.next!=null){
ListNode temp = head.next;
head.next.next = head;
head = temp;
}
return head;
}
}
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode curr = head;
while(curr!=null){
ListNode temp = curr.next;
curr.next = pre;
pre = curr;
curr = temp;
}
return pre;
}
}
image.png
第二種解決辦法 利用遞歸來實現(xiàn)
遞歸理解起來的話绑雄，有點類似于從這個鏈表的尾節(jié)點開始唧取，例如鏈表是
1->2->3->4
那么遞歸調(diào)用铅鲤，從4開始到1，每個執(zhí)行 head.next.next = head來反轉(zhuǎn)鏈表枫弟。
注意邢享，一定要head.next=null,否則會造成循環(huán)鏈表。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
//利用遞歸來實現(xiàn)反轉(zhuǎn)鏈表
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode temp = reverseList(head.next);
head.next.next=head;
head.next = null;
return temp;
}
}
image.png
