1. 力扣206 : 反转链表
(1). 题 : 图略
给你单链表的头节点 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 :
该解法的空间复杂度比较高(O(n)), 因为借助了int[n]大小的数组.但空间换时间, 该解法的时间复杂度较低(O(n)).只有for一层循环.
思路 : 首先遍历链表，得到链表节点的个数，借助数组存储原链表的节点的数据域，再for循环覆盖原链表的节点的数据域.
解 :
class Solution { public ListNode reverseList(ListNode head) { ListNode p; int count = 0; for (p = head; p != null; p = p.next) { count++; } int newCount = count; int[] arr = new int[count]; count = 0; for (p = head; p != null; p = p.next) { arr[count++] = p.val; } count = 0; for (p = head; p != null; p = p.next) { p.val = arr[newCount - 1]; newCount--; } return head; } }
解法2 : 可以使用递归来解决.以示例1为例.
思路 : 不断递归, 当递归到head指向节点5时(最后一个节点), 返回节点5, last指向节点5, 此时head指向节点4, 将节点5指向节点4, 节点4的指针域设置为null, 返回last指针.
解 :
class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode last = reverseList(head.next); head.next.next = head; head.next = null; return last; } }
解法3 : 迭代+双指针
思路 : n1初始时指向空，o1记录头节点的下一个节点，不断将原链表的节点头插到空链表中，并更新n1使得其指向该链表的头节点.
解法 :
class Solution { public ListNode reverseList(ListNode head) { if (head == null) { return head; } ListNode n1 = null; while (head != null) { ListNode o1 = head.next; head.next = n1; n1 = head; head = o1; } return n1; } }
2. 力扣203 : 移除链表元素
题 : 图略
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5] 示例 2： 输入：head = [], val = 1 输出：[] 示例 3： 输入：head = [7,7,7,7], val = 7 输出：[] 提示： 列表中的节点数目在范围 [0, 104] 内 1 <= Node.val <= 50 0 <= val <= 50
解法1 : 迭代
思路 : 增加哨兵节点, 使得处理头节点变得简单.想要删除一个节点, 得找到想要删除节点的上一个节点, 从哨兵节点开始, 如果其下一个节点的数据域为val, 则删除, 否则将指针移到下一个节点.
解 :
class Solution { public ListNode removeElements(ListNode head, int val) { //增加头节点 if (head == null) { return null; } //哨兵节点 ListNode dummy = new ListNode(0); dummy.next = head; ListNode temp = dummy; while (temp.next != null) { if (temp.next.val == val) { temp.next = temp.next.next; } else { temp = temp.next; } } return dummy.next; } }
解法2 : 递归
思路 : 基线条件，如果head为null，则返回null.如果我(当前head所在节点)的数据域与val相等，则返回我的下一个节点的递归结果.如果我的数据域与val不想等，则返回我与我的下一个节点的递归结果.
解 :
class Solution { public ListNode removeElements(ListNode head, int val) { if (head == null) { return head; } //如果我与val相等, 返回下一个节点的递归结果 if (head.val == val) { return removeElements(head.next, val); } else { //如果我与val不相等, 则返回我以及我的下一个节点的递归结果 head.next = removeElements(head.next, val); return head; } } }
3. 力扣19 : 删除链表的倒数第n个节点
题 :
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 示例 1： 输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2： 输入：head = [1], n = 1 输出：[] 示例 3： 输入：head = [1,2], n = 1 输出：[1] 提示： 链表中结点的数目为 sz 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz 进阶：你能尝试使用一趟扫描实现吗？
解法1 : 双指针(快慢指针)
注 : 题目中n是合法的, 所以无需考虑n不合法的情况.
思路 : 设置哨兵节点, 为了方便删除头节点的操作.初始时, 快慢指针均指向哨兵节点, fast指针先动,然后快慢指针一起移动, 当fast指针指向最后一个节点时, slow指针刚好指针待删除节点的上一个节点.
解 :
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { //设置哨兵节点 ListNode dummy = new ListNode(0); dummy.next = head; ListNode fast = dummy; ListNode slow = dummy; while (n-- > 0) { fast = fast.next; } while (fast.next != null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return dummy.next; } }
解法2 : 递归
思路 : 当p为null时, 返回0, t＝0(此时p指向倒数第一个节点), 返回1, 即倒数第几个节点就返回几，而此时p指向该倒数节点的上一个节点，所以可以对要删除的节点进行删除操作.
解 :
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { //设置哨兵节点 ListNode dummy = new ListNode(0, head); recursion(dummy, n); return dummy.next; } public int recursion(ListNode p, int n){ if (p == null) { return 0; } int t = recursion(p.next, n); if (t == n) { p.next = p.next.next; } return t + 1; } }
