leetcode 206題。 翻轉(zhuǎn)鏈表

leetcode鏈接用于測(cè)試

題目：描述
將一個(gè)鏈表翻轉(zhuǎn)：

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

遞歸解法

解題思路。遞歸每個(gè)子過程執(zhí)行的都是相同的過程，只要我們?cè)谶f歸時(shí)，保證一個(gè)節(jié)點(diǎn)實(shí)現(xiàn)翻轉(zhuǎn)，遞歸下去就會(huì)全部翻轉(zhuǎn)過來，
所以就可以寫出遞歸過程了，

leetcode 提供的鏈表結(jié)構(gòu)：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/

遞歸代碼演示

class Solution {public ListNode reverseList(ListNode head) {//base case 節(jié)點(diǎn)為null或者只有一個(gè)節(jié)點(diǎn)時(shí) 無需翻轉(zhuǎn)，返回自身if(head == null || head.next == null){return head;}//遞歸去操作每一個(gè)節(jié)點(diǎn)ListNode last = reverseList(head.next);//節(jié)點(diǎn)翻轉(zhuǎn)head.next.next = head;head.next = null;return last;}
}

普通方式實(shí)現(xiàn)鏈表翻轉(zhuǎn)

class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null){return head;}ListNode pre = null;ListNode cur = head;ListNode next = null;while(cur != null){next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}
}

鏈表專題

leetcode–分隔鏈表

leetcoe–合并 K 個(gè)升序鏈表

leetcode–刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)