- 反转链表
给你单链表的头节点 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
写法一：不使用头节点，可以看到需要三个变量
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
ListNode pre = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
写法二：使用头节点，你可以发现用了四个变量，因为你需要使用dummy.next来返回
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy, cur = pre.next;
while (cur != null && cur.next != null) {
ListNode next = cur.next;
cur.next = cur.next.next;
next.next = pre.next;
pre.next = next;
}
return dummy.next;
}
}
写法三：使用递归的方法，最简洁，但需要思考
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode re = reverseList(head.next);
head.next.next = head;
head.next = null;
return re;
}
}
- 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
提示：
链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
写法一：使用头节点，可以看出来很简单
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode pre = new ListNode(0, head);
ListNode dummy = pre;
int cnt = right - left;
while (left-- > 1) {
pre = pre.next;
}
ListNode cur = pre.next;
for (int i = 0; i < cnt; i++) {
ListNode next = cur.next;
cur.next = cur.next.next;
next.next = pre.next;
pre.next = next;
}
return dummy.next;
}
}
写法二：对反转链表的不使用头节点有很深的理解，我最开始就是用的这种
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode start = head, end = head;
ListNode prefix = new ListNode(0, head);
int temp = left;
while (left-- > 1) {
prefix = prefix.next;
start = start.next;
}
while (right-- > 1) {
end = end.next;
}
ListNode last = end.next;
ListNode pre = last;
while (start != last) {
ListNode next = start.next;
start.next = pre;
pre = start;
start = next;
}
if (temp == 1) return pre;
prefix.next = pre;
return head;
}
}