BM1 反转链表
解题思路
第一种方法：借助栈
1. 栈的特点是先进后出，用stack来存储链表，之后新建一个头节点，按出栈顺序拼接形成新的链表。
2. 注意，最后一个节点的next要赋值null
3. 空间复杂度O(N), 时间复杂度O(N)
JAVA代码实现
import java.util.*;
public class Solution {public ListNode ReverseList (ListNode head) {// 用栈，空间复杂度O(N),时间复杂度O(N)Stack<ListNode> stack = new Stack<>();while(head != null){stack.push(head);head = head.next;}//出栈，重新连接if(stack.isEmpty()){return null;}ListNode node = stack.pop();ListNode dummy = node;while(!stack.isEmpty()){ListNode tempNode = stack.pop();node.next = tempNode;node = node.next;}//最后一个下一位为空node.next = null;return dummy;}
}
第二种方法，修改链表指针指向；
指针cur表示当前要处理的节点
指针tmp用于暂存cur.next,避免后面修改指针后，断链无法继续遍历
指针pre表示当前处理节点的上一个节点，进行翻转的目的是将cur.next修改成pre
初始化时，我们将pre设为null，因为第一个节点最后变成最后一个节点，其next为null
import java.util.*;
public class Solution {public ListNode ReverseList (ListNode head) {//双指针迭代，空间复杂度O(1),时间复杂度O（N）//前继节点为pre，当前操作节点为cur//初始化cur为head，pre=nullListNode cur = head, pre = null;while(cur != null){ListNode nextNode = cur.next;//存储下一个节点,不然局部反转的时候会断链cur.next = pre;pre = cur;cur = nextNode;}return pre;}
}
BM2 链表内指定区间反转
解题思路
在上一题的基础上进行修改
首先，要处理的cur节点先走m步走到第m个节点
反转结束的条件不是链表遍历到末尾null时候，而是遍历到第n个节点就结束
没有结束额外空间，空间复杂度O(1), 时间复杂度O(N)
import java.util.*;
public class Solution {public ListNode reverseBetween (ListNode head, int m, int n) {// write code here//可以用BM1 反转链表的思想，ListNode dummy = new ListNode(-1);dummy.next = head;ListNode pre = dummy;ListNode cur = head;//找mfor (int i = 1; i < m; ++i) {pre = cur;cur = cur.next;}//反转m到nfor (int i = m; i < n; ++i) {ListNode temp = cur.next;cur.next = temp.next;temp.next = pre.next;pre.next = temp;}return dummy.next;}
}
BM3 链表中的节点每k个一组翻转
解题思路
参考了官方解题，递归翻转
设置一个遍历的尾指针tail，每次反转之前找到翻转区间的最后一个节点
如果tail在k步内变成了null，则直接返回，不进行翻转（最后一段不足k个，不翻转）
之后与BM1一样，定义pre，cur，翻转结束的条件是当走到tail，停止翻转
递归的返回值是当前翻转这一分组的头结点
这道题还不是很理解，后面有新的理解再重新整理笔记
import java.util.*;
public class Solution {public ListNode reverseKGroup (ListNode head, int k) {// write code hereListNode tail = head;//反转的尾部//遍历k次到尾部for (int i = 0; i < k; ++i) {//如果不足k到了尾部，则不翻转if (tail == null) {return head;}tail = tail.next;}ListNode pre = null;ListNode cur = head;while (cur != tail) {//到达尾部前ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}//当前尾指向下一段要翻转的链表head.next = reverseKGroup(tail,k);return pre;}
}
BM4 合并两个排序的链表
解题思路
比较简单，新建一个链表，同时遍历两个链表，比较val的大小，遇到较小的就加入；
import java.util.*;
public class Solution {public ListNode Merge (ListNode pHead1, ListNode pHead2) {// write code hereListNode res = new ListNode(-1);ListNode dummy = res;while(pHead1 != null && pHead2 != null){if(pHead1.val <= pHead2.val){dummy.next = pHead1;pHead1 = pHead1.next;}else{dummy.next = pHead2;pHead2 = pHead2.next;}dummy = dummy.next;}if(pHead1 != null){dummy.next = pHead1;}if(pHead2 != null){dummy.next = pHead2;}return res.next;}
}
BM6 判断链表中是否有环
解题思路
是的，没有BM5,因为它是难题，菜的一批的我看答案也还没理解透
利用双指针，slow每次往前走一步，fast每次往前走两步，如果链表中有环，则两个指针最终会在非终点的地方相遇
因为地球是圆的，slow和fast不是平行走，总会在一个时间点遇到的，时长的问题而已
双指针在后面很多题目中都会遇到过。
import java.util.*;
public class Solution {public boolean hasCycle(ListNode head) {//快慢指针ListNode fast = head;ListNode slow = head;if(head == null){return false;}// fast.next = head;// slow.next = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(slow == fast){return true;}}return false;}
}
BM7 链表中环的入口结点
解题思路
还有借助双指针slow和fast，之后要寻找规律
假设双指针在结点C相遇，且slow是第一次走到C，A->B的距离为X，B->C的距离为Y
则slow走了X+Y，fast每次走的是slow的两倍，所以fast走了2*（X+Y）
fast走的2*（X+Y）实际路径是A->B B->C C->B B->C，我们不知道的是C->B的距离，根据上述条件，可以知道
C->B的距离= 2*（X+Y）-（A->B）-(B->C) -(B->C)= 2*（X+Y）-X-Y-Y=X
噢，原理规律就是，相遇点C->B（环入口）的距离，竟然等于从头结点到环入口的距离
那好办了，slow还是在C开始走，fast回到头结点，和slow一起一步一步走，走到他俩遇见的结点，就是环的入口结点。破案。
import java.util.*;
public class Solution {public ListNode EntryNodeOfLoop(ListNode pHead) {//双指针 空间O(1) 时间O(N)if(pHead == null || pHead.next == null){return null;}ListNode fast = pHead;ListNode slow = pHead;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;//有环，双指针会在环中相遇if(slow == fast){break;}}if(fast == null || slow == null){return null;}fast = pHead;//与第一次相遇的节点相同速度出发，相遇节点为入口结点while(fast != slow){fast = fast.next;slow = slow.next;}return fast;}
}
还有一种办法是，不断的遍历链表，借助集合，存储遍历到的结点；
每遍历一个结点判断当前集合中是否已经有这个结点，有的话直接return。
public ListNode EntryNodeOfLoop(ListNode pHead) {//hash 空间O(N) 时间O(N)HashSet<ListNode> set = new HashSet<>();while(pHead != null){if(set.contains(pHead)){return pHead;}set.add(pHead);pHead = pHead.next;}return null;}
BM8 链表中倒数最后k个结点
解题思路
两次循环，先统计长度，之后遍历到count-k处，return
public ListNode FindKthToTail (ListNode pHead, int k) {// 最简单的想法，但是需要两次遍历//先遍历，看链表长度，然后遍历count-k次，returnListNode dummy = pHead;if(pHead == null){return pHead;}int count = 1;while(dummy.next != null){count++;dummy = dummy.next;}if(count < k){return null;}dummy = pHead;while(count > k){dummy = dummy.next;count --;}return dummy;}
双指针
fast先走k步
之后fast和slow一起走，当fast走到链表尾部时，slow所在的结点刚好是倒数第k个
public class Solution {public ListNode FindKthToTail (ListNode pHead, int k) {//快慢指针if(pHead == null){return pHead;}ListNode fast = pHead;ListNode slow = pHead;while(k-- > 0){if(fast != null){fast = fast.next;}else{return null;}}while(fast != null){fast = fast.next;slow = slow.next;}return slow;}
}
BM9 删除链表的倒数第n个节点
解题思路
双指针
注意，有可能删除第1个结点，所以定义一个虚拟头结点res
fast从res开始，先走n步
实际上就是从head开始走了n-1步
当fast走到链表尾部时，slow就走到了倒数第n-1个结点,跳过第n个结点即可：slow.next = slow.next.next
import java.util.*;
public class Solution {public ListNode removeNthFromEnd (ListNode head, int n) {// 双指针//注意有可能删除第一个，所以使用一个头节点if(head == null){return head;}ListNode res = new ListNode(-1);res.next = head;ListNode slow = res;ListNode fast = res;//fast先走n步for(int i=0;i<n;i++){fast = fast.next;}while(fast.next != null){fast = fast.next;slow = slow.next; }slow.next = slow.next.next;return res.next;}
}
BM10 两个链表的第一个公共结点
解题思路
第一种方法是先遍历两个链表的长度len1和len2；
如果len1>len2, 链表1先走len1-len2步，因为公共部分在尾部，要尾部对齐；
之后同时遍历链表1和链表2，如果遇到两者相等，直接return（有公共结点会返回，没有会一起走到尾部，返回null）
代码较为繁琐，也可能是我太菜了，不会优化
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {//1.先统计两个链表的长度len1,len2ListNode dummy1 = pHead1;ListNode dummy2 = pHead2;int len1 = 0;while(dummy1 != null){dummy1 = dummy1.next;len1++;}int len2 = 0;while(dummy2 != null){dummy2 = dummy2.next;len2++;}//2,较长的链表，指针先走|len1-len2|,因为链表的公共部分在尾部，尾部对齐dummy1 = pHead1;dummy2 = pHead2;if(len1 > len2){while(len1 - len2 > 0){dummy1 = dummy1.next;len1--;}}if(len1 < len2){while(len2 - len1 > 0){dummy2 = dummy2.next;len2--;}}//3.两个链表同时移动，如果遇到节点相同，return，如果有一方已经=null，直接return nullwhile(dummy1 != null && dummy2 != null){if(dummy1 == dummy2){return dummy1;}else{dummy1 = dummy1.next;dummy2 = dummy2.next;}}return null;}
第二种方法，还是双指针，找规律
链表1的长度为len1，链表2的长度为len2，
指针n1和指针n2，一个从链表1出发，一个从链表2出发，两者都走len1+len2个长度
如果有公共结点，如样例{1,2,3}{4,5}{6,7}
/n1走：1，2，3，6，7，null，4，5，6
n2走：4，5，6，7，null，1，2，3，6
走到相等的时候就是公共起始点
没有公共节点如{1}{2,3},{},n1:1,2,3，null n2:2,3,1，null 走到最后相等都为空
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {ListNode n1 = pHead1;ListNode n2 = pHead2;while(n1 != n2){n1 = (n1 == null)? pHead2 : n1.next;//n1第一次走到空的时候是phead1遍历完n2 = (n2 == null)? pHead1 : n2.next;}return n1;}
}
BM11链表相加(二)
解题思路
先把两个链表进行翻转，这样就可以按位加
每个链表结点存储的值在0-9，所以如果计算出来超过9，需要借助变量isTen记录超过9的十位数是多少
链表结点的值取当前位置两个值相加+isTen之后的个位数
import java.util.*;
public class Solution {public ListNode addInList (ListNode head1, ListNode head2) {// write code herehead1 = reverse(head1);head2 = reverse(head2); ListNode ans = new ListNode(-1);ListNode dummy = ans;int isTen = 0;int val=0;while(!(head1 == null && head2 == null)){val = isTen;if(head1 != null){val += head1.val;head1 = head1.next;}if(head2 != null){val += head2.val;head2 = head2.next;}isTen = val/10;dummy.next = new ListNode(val%10);dummy = dummy.next;}if(isTen > 0){dummy.next = new ListNode(isTen);}return reverse(ans.next);}public ListNode reverse(ListNode head){if(head == null){return head;}ListNode cur = head;ListNode per = null;while(cur!= null){ListNode tmp = cur.next;cur.next = per;per = cur;cur = tmp;}return per;}
}
BM12 单链表排序
解题思路
借助数组，存储当前链表的所有结点值
对数组进行排序
重新建立链表返回
public class Solution {public ListNode sortInList (ListNode head) {// 借助数组ListNode dummy = head;List<Integer> list = new ArrayList<>();while(dummy != null){list.add(dummy.val);dummy = dummy.next;}Collections.sort(list);dummy = head;for(int i=0;i<list.size();++i){dummy.val = list.get(i);dummy = dummy.next;}return head;}
}
BM13 判断一个链表是否为回文结构
解题思路
借助栈，先将链表的节点值依次入栈
之后，从头遍历链表，将其值与栈顶元素相比，如果相等则继续遍历，栈顶元素出栈；否则直接return false
public boolean isPail (ListNode head) {// write code here//借助一个栈，空间复杂度O(N)，时间复杂度O(N)Stack<Integer> stack = new Stack();if(head == null){return true;}ListNode dummy = head;while(dummy != null){stack.push(dummy.val);dummy = dummy.next;}dummy = head;while(!stack.isEmpty()){if(stack.pop() != dummy.val){return false;}dummy = dummy.next;}return true;}
方法二，快慢指针
slow每次走一步，fast每次走两步
fast走到链表末尾时，slow走到链表中间
将slow到fast的子链表进行翻转，翻转后的第一个结点由slow指向
之后fast从原始链表头结点开始遍历，判断slow与fast是否相等
public class Solution {public boolean isPail (ListNode head) {// write code here//双指针，slow往后一步，fast走两步，当fast走到末尾时，slow走到中间//后半段进行反转//时间复杂度O(N) 空间复杂度O(1)if (head == null || head.next == null) {return true;}ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}slow = reverse(slow);fast = head;while (slow != null && fast != null) {if (slow.val != fast.val) {return false;}slow = slow.next;fast = fast.next;}return true;}public ListNode reverse(ListNode head) {ListNode per = null;ListNode cur = head;while (cur != null) {ListNode tmp = cur.next;cur.next = per;per = cur;cur = tmp;}return per;}
}
