链表题型思路错误总结
常见题目
206. 反转链表
关键点：定义前置指针。
在给cur.next复制前，需要定义好next节点防止断链。
public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode pre = null;ListNode cur = head;while(cur!=null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}
21. 合并两个有序链表
关键点：需要一个实质的头节点
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) {return l2;}if (l2 == null) {return l1;}ListNode pre = new ListNode();ListNode cur = pre;while (l1 != null && l2 != null) {if (l1.val < l2.val) {cur.next = l1;l1 = l1.next;} else {cur.next = l2;l2 = l2.next;}cur = cur.next;}while (l1 != null) {cur.next = l1;l1 = l1.next;cur = cur.next;}while (l2 != null) {cur.next = l2;l2 = l2.next;cur = cur.next;}return pre.next;}
}
109. 有序链表转换二叉搜索树
关键点：如何对链表进行分割。
class Solution {public TreeNode sortedListToBST(ListNode head) {if (head == null) {return null;}if (head.next == null) {return new TreeNode(head.val);}return curser(head, null);}private TreeNode curser(ListNode head, ListNode tail) {if (head == tail) {return null;}ListNode slow = head;ListNode fast = head;while(fast != tail && fast.next != tail) {slow = slow.next;fast = fast.next.next;}TreeNode root = new TreeNode(slow.val);root.left = curser(head, slow);root.right = curser(slow.next, tail);return root;}}
234. 回文链表
思路1：转换成数组，按照定义进行判断
class Solution {public boolean isPalindrome(ListNode head) {if(head == null || head.next == null){return true;}int length = 0;ListNode cur = head;while (cur != null) {length ++;cur = cur.next;}int[] array = new int[length];cur = head;for (int i = 0; i < length; i++) {array[i] = cur.val;cur = cur.next;}for (int i = 0; i < length/2; i++) {if(array[i] != array[length - i - 1]) {return false;}}return true;}
}
思路2：找到中间节点，进行反转
为什么设置：ListNode slow = head; ListNode fast = head.next; 而不是ListNode slow = head; ListNode fast = head;
- 找到需要反转链表的前一个，为了统一
1 3 5 3 1是找到了饭互赞链表的前一个，但是1 2 2 1却找到了需要反转的当前这个。
所以需要将fast往后移动一位，如下：
class Solution {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}// 找到中间节点ListNode slow = head;ListNode fast = head.next;while(fast !=null && fast.next != null) {slow = slow.next;fast = fast.next.next;}// 反转后半部分ListNode second = slow.next;slow.next = null;second = reverse(second);while(second != null) {if (head.val != second.val){return false;}second = second.next;head = head.next;}return true;}private ListNode reverse(ListNode head){if(head == null ||head.next == null){return head;}ListNode pre = null;ListNode cur = head;while(cur != null){ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}
}
876. 链表的中间结点
思路：如上题解题思路
class Solution {public ListNode middleNode(ListNode head) {if (head == null || head.next == null) {return head;}// 找到中间节点ListNode slow = head;ListNode fast = head;while(fast !=null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}
}
19. 删除链表的倒数第 N 个结点
- 为什么新加一个头结点
- 为了防止删除第一节点，例如n = 5时，不好操作，加一个头结点有些解决这类问题。添加头结点
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if (head == null){return head;}ListNode pre = new ListNode();pre.next = head;ListNode cur = pre;ListNode fast = head;for (int i = 0; i < n; i++) {if (fast != null) {fast = fast.next;}}while(fast != null) {cur = cur.next;fast = fast.next;}cur.next = cur.next.next;return pre.next;}
}
86. 分隔链表
class Solution {public ListNode partition(ListNode head, int x) {if (head == null) {return head;}ListNode l1 = new ListNode();ListNode l2 = new ListNode();ListNode cur = head;ListNode small = l1;ListNode big = l2;while(cur != null) {ListNode next = cur.next;if (cur.val < x) {small.next = cur;small = small.next;} else {big.next = cur;big = big.next;}cur.next = null;cur = next;}small.next = l2.next;return l1.next;}
}
92. 反转链表 II
- left需要指向移动前一个，right移动到需要反转的位置。
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {if (head == null || head.next == null) {return head;}ListNode pre = new ListNode();pre.next = head;ListNode le = pre;ListNode rt = pre;for (int i = 0; i < left - 1; i++){le = le.next;}ListNode l1 = null;if(le != null) {l1 = le.next;}for (int i = 0; i < right; i++){rt = rt.next;}ListNode l2 = null;if(rt != null) {l2 = rt.next;rt.next = null;}le.next = reverseListNode(l1);l1.next = l2;return pre.next;}private ListNode reverseListNode(ListNode head) {if (head == null || head.next == null) {return head;}ListNode pre = null;ListNode cur = head;while(cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}
}