2021.01.03
今日题目：给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。
自己的思路：
自己的菜鸡代码🈶🈚
2021.01.04
今日题目：从尾到头打印单链表【简单】
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
- 思路：
- 法一：因为要用数组返回每个结点的值，所以先获取整个单链表的长度（ 时间复杂度为O(n) ），然后从头遍历单链表，同时从尾到头在数组中存放遍历结果，这里利用的是数组连续存放的特性。（这个算是暴力法了吧）
剑指中提到的另外两种解法——有利用题干中从头到尾遍历和从尾到头输出的特性。
- 法二：链表只能从头到尾遍历，而要求的是从尾到头输出数据，符合栈的特性（后进先出），故可以用一个栈保存遍历的结果，然后再输出结果。
- 法三：法二中提到用栈来解决，而由栈联想到递归，故也可以用递归进行解决。递归的代码很简单，但是若是链表的长度过长，则会导致函数递归调用的层级很深，从而可能导致函数调用栈溢出。（不提倡使用）
- 自己的菜鸡代码：
```java
// 法一的代码
/**
- Definition for singly-linked list.
- public class ListNode {
- int val;
- ListNode next;
- ListNode(int x) { val = x; }
- }
*/
class Solution {
public int[] reversePrint(ListNode head) {
} }ListNode p = head;int length = 0;while(p != null){++length;p = p.next;}int result[] = new int[length];p = head;for(int i = length-1; i >= 0; i--){result[i] = p.val;p = p.next;}return result;
// 法三的代码 class Solution { public int[] reversePrint(ListNode head) { if(head != null){ if(head.next != null){ reversePrint(head.next); } System.out.println(head.val); } } }
运行结果：<br /><a name="oKgok"></a>### 2021.01.04今日题目：链表中倒数第k个结点【简单】<br />输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。<br />- 思路（双指针）：使用两个临时变量temp与tag，首先两个同时指向头结点，设定一个计数器，然后temp向后遍历至第k个结点停止遍历。查看计数器的值，若计数器的值大小于k则表示k的值大于链表的长度，为无效值；若此时计数器的值等于k，则temp与tag同时向后遍历，若temp指向最后一个结点，则表示tag所指结点即为倒数第k个结点。- 自己的菜鸡代码：```javaclass Solution {public ListNode getKthFromEnd(ListNode head, int k) {ListNode temp,tag;tag = temp = head;int count = 1;for(; count < k && temp.next != null; count++,temp = temp.next) ;if(count < k) return null;// k大于链表长度，为无效值System.out.println(temp.val);while(temp.next != null){temp = temp.next;tag = tag.next;}return tag;}}
运行结果：
2021.01.06 合并两个排序的链表
今日题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
提示：0 <= 链表长度 <= 1000
- 思路：因为L1和L2都是不带头节点的单链表，所以先判断两个单链表是否都不为空，在都不为空的情况下，比较两个头结点的大小，选择值较小的结点作为新链表的头结点（例如 L1.val 较小），同时用一个head指针指向头结点，用一个尾指针rear记录新链表的最后一个结点，便于插入，使L1指向下一个结点，然后以L1不为空且L2不为空为循环条件，比较L1与L2值的大小，rear结点的next值指向较小值的结点，该较小值结点要从旧链表中剥离。最后若L1单链表中还有值，直接把剩下部分加入新链表的末尾；若L2单链表中还有值，则直接把剩下的部分加入新链表的末尾。时间复杂度为 O(min{n,m});
自己的菜鸡代码：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1 == null) return l2;if(l2 == null) return l1;ListNode rear, head;if(l1.val < l2.val) {rear = l1;l1 = l1.next;}else{rear = l2;l2 = l2.next;}head = rear;rear.next = null;while(l1 != null && l2 != null){if(l1.val < l2.val){rear.next = l1;l1 = l1.next;}else{rear.next = l2;l2 = l2.next;}rear = rear.next;}if(l1 != null){rear.next = l1;l1 = l1.next;}else{rear.next = l2;l2 = l2.next;}return head;}}
运行结果：
2021.01.06 两个链表的第一个公共结点
今日题目：输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
注意：
- 如果两个链表没有交点，返回 null.
- 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
思路：
- 法一：暴力法。遍历一个单链表A，然后在B中逐个查找是否有公共结点。时间复杂度为O(n*m);空间复杂度为O(1)；
- 法二：使用两个栈，然后保存遍历的结果，判断栈顶元素的值是否相等，若是不等直接返回null表示没有交点，若是相等，直至找到不相等的结点。时间复杂度为O(n)；空间复杂度为O(n)；以空间换时间。（这个方法也蛮恶心的）
- 法三：（努力找寻时间复杂度为O(n)，空间复杂度为O(1)的算法）看评论区大佬的思路，用双指针ptrA与ptrB分别指向两个链表的头结点，同时向后遍历，若ptrA或ptrB遍历结束，则继续从另一条链表的头结点出发继续遍历，两个指针会在两个链表第一个公共结点处相遇。时间复杂度为O(m+n)，空间复杂度为O(1)。大佬示意图如下：
- 自己的菜鸡代码：
```java
/**
- Definition for singly-linked list.
- public class ListNode {
- int val;
- ListNode next;
- ListNode(int x) {
- val = x;
- next = null;
- }
- } */
// 法一：暴力美学 public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null) return null; ListNode ptrB; for(ListNode ptrA = headA; ptrA != null; ptrA = ptrA.next){ for(ptrB = headB; ptrB != null; ptrB = ptrB.next){ if(ptrB == ptrA) return ptrA; } } return null; } }
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 法二(也很恶心)
if(headA == null || headB == null) return null;
ListNode ptr1 = headA, ptr2 = headB;
Stack
if(ptr1 != ptr2) return null;return ptr1;}
}
// 法三，太强了 public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 法三（震撼我妈） if(headA == null || headB == null) return null; ListNode ptrA = headA, ptrB = headB; while(ptrA != ptrB){ ptrA = ptrA != null? ptrA.next : headB; ptrB = ptrB != null? ptrB.next : headA; } return ptrA; } }
- 运行结果：法一（左，惨不忍睹）：<br />法二（右，空间复杂度很不行）<br /><br />法三（这就是算法的魔力吗，祝天下有情人终成眷属）：<br /><a name="XheIW"></a>### 2021.01.07今日题目：反转链表<br />定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。<br /><br />提示：0 <= 节点个数 <= 5000- 思路：1. 法一：遍历一遍链表，同时采用头插法重建链表，遍历结束即成功反转该链表。时间复杂度O(n)，空间复杂度O(1)。1. 法二：看到评论区有大佬说可以用递归的方式处理（zhwm）。假设链表的其余部分已经反转，那么要如何反转前面的部分。假设列表为n →…→n →n→n→…→n →∅<br />若从节点 n到n已经被反转，而我们正处于nk。n→…→n→n→n←…←n<br />我们希望n的下一个节点指向n。所以n.next.next=n要小心的是n的下一个必须指向∅ 。<br />如果忽略了这一点，链表中可能会产生循环。如果使用大小为 2 的链表测试代码，则可能会捕获此错误。时间复杂度O(n)，空间复杂度O(n)。<br />递归的方式很不好理解。（偷大佬的示意图）（这里再加个自己理解的图）1. 法三：妖魔化的双指针。时间复杂度O(n)，空间复杂度O(1)。- 自己的菜鸡代码：```java/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/// 法一class Solution {public ListNode reverseList(ListNode head) {if(head == null) return head;ListNode p = head.next, q;head.next = null;while(p != null){q = p.next;p.next = head;head = p;p = q;}return head;}}// 法二（递归实现，不好理解）class Solution {public ListNode reverseList(ListNode head) {// 前一个判断单链表是否为空，后一个判断是否已经递归到最后一个结点if(head == null || head.next == null) return head;ListNode ret = reverseList(head.next);head.next.next = head;head.next = null;return ret;}}// 法三（妖魔化双指针即不用头插法的方式）class Solution {public ListNode reverseList(ListNode head) {// 不同的双指针方法if(head == null) return null;ListNode p = head, q;while(head.next != null){q = head.next.next;head.next.next = p;p = head.next;head.next = q;}return p;}}
- 运行结果：
法一、法二、法三
2021.01.07
今日题目：删除链表的结点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
说明：题目保证链表中节点的值互不相同，若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点。
- 思路：首先判断链表是否为空。在不为空的情况下，判断头结点是否为待删除结点，若是则直接返回 head.next ，否则遍历单链表，直到找到待删除结点，将其从单链表中剥离即可。
自己的菜鸡代码：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/class Solution {public ListNode deleteNode(ListNode head, int val) {// 要注意删除的值是否为头结点的情况if(head == null) return null;if(head.val == val) return head.next;ListNode p = head;while(p.next != null){if(p.next.val == val){p.next = p.next.next;break;}p = p.next;}return head;}}
运行结果：
若有收获，就点个赞吧
0 人点赞
