206.反轉鏈表

題目

給你單鏈表的頭節點 head ，請你反轉鏈表，并返回反轉后的鏈表。

示例

示例1

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

示例2

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

示例3

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

提示

• 鏈表中節點的數目范圍是 [0, 5000]
• -5000 <= Node.val <= 5000

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

解答

1. 遞歸的終止條件是當前節點或者下一個節點==null
2. 在函數內部，改變節點的指向，也就是 head 的下一個節點指向 head 遞歸函數那句
3. 返回新的節點

使用遞歸解答（Java）

/*** 定義節點類*/
@AllArgsConstructor
@NoArgsConstructor
@ToString
public class ListNode {int val;ListNode next;
}class Solution {/*** 反轉鏈表* @param head 頭節點* @return  反轉后的頭節點*/public ListNode reverseList(ListNode head) {// 使用遞歸(如果節點為空 那么返回null)if(head.next == null){return head;}// 創建新的節點(依次往下進行尋找 找到最后一個節點)ListNode newLinkedNode = reverseList(head.next);// 將最后一個節點的next指向當前節點head.next.next = head;// 將當前節點的next指向nullhead.next = null;// 返回新的節點return newLinkedNode;}@Test@DisplayName("測試-反轉鏈表")public void test(){ListNode head = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5,null)))));ListNode result = reverseList(head);System.out.println("result.toString() = " + result.toString());}
}