bm1
解题思路
整个链表反转，套路是定义pre和cur指针，cur先往前指，然后pre指向cur，cur指向正向链表的next，一轮遍历就可以反转掉链表
核心点
//1.先获取当前值的next,指向temp
temp=cur.next
//2.将当前值的next指向pre,就相当于做反转
cur.next = pre
//3.将pre指向cur，最终是要返回pre的，pre指针一直在往后移动
pre = cur
//4.将cur指向temp，进入下一个循环，继续往后遍历
代码
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
//第一步，定义temp
ListNode temp = cur.next;
//第2步,把cur.next指向pre
cur.next = pre;
//第3步，pre指向cur
pre = cur;
//第4步，把cur指向temp
cur = temp;
}
return pre;
}
public class ListNode {
public int val;
public ListNode next = null;
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public ListNode getNext() {
return next;
}
public void setNext(ListNode next) {
this.next = next;
}
}
bm2
解题思路
使用抽书法，比如1234567，m=3,n=5,最终反转345，最后的链表结构是1254367
需要反转的是345，反转成543
第一次反转，需要3次交换，3->4变成3->5, 4->5变成4->3, 2->3变成2->4，第一次反转之后链表是1243567
image.png
第2次反转，链表变成了1243567，3->5变成3->6, 5->6变成5->4, 2->4变成2->5，反转完成
image.png
核心点
//1.使用一个虚拟头结点的概念，最终返回一个dummy.next即可
ListNode dummy = new ListNode(-1);
dummy.next = head;
//2.确定pre的位置，链表从1开始的，使用一个for循环，到m-1结束循环，获取pre的值
ListNode pre = dummy ;
for(i=0;i<m-1;i++) {
pre = pre.next;
}
//3.开始循环进行交换
ListNode cur = pre.next;
for(i=0;i<n-m;i++) {
//3.1.先确定temp;
ListNode temp = cur.next;
//3.2.cur.next指向temp.next;
cur.next = temp.next;
//3.3.temp.next指向cur
temp.next = pre.next;
//3.4.pre.next指向temp;
pre.next=temp;
}
//4.返回dummy.next结束
代码
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
for (int i = 0; i < m - 1; i++) {
pre = pre.next;
}
ListNode cur = pre.next;
ListNode temp;
for (int i = 0; i < n - m; i++) {
//tmp是cur的next
temp = cur.next;
//第1步，把cur.next指向temp.next
cur.next = temp.next;
//第2步，将tmp的next指向cur
temp.next = pre.next;
//第3步，把pre.next指向tmp
pre.next = temp;
}
return dummy.next;
bm3
解题思路
相当于拆成k个bm1的子过程，不过第一组翻转过后的尾节点，要指向第二组翻转过后的头节
使用递归，确定递归的终止条件，然后每个子任务其实就相当于bm1了，最后递归将每个组的Head串起来
核心点
ListNode tail = head;
//1.递归终止条件
for (int i = 0; i < k; i++) {
if (tail == null) {
return head;
}
//tail继续往后移,经过一个for循环，tail就变成了下一个组的head了
tail = tail.next;
}
//2.bm1反转链表，将每个组进行链表反转
ListNode pre = null;
ListNode cur = head;
for (int i = 0; i < k; i++) {
if (cur != tail) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
}
//3.递归，将第一组的尾节点指向第2组的头节点
head.next = reverseKGroup(tail, k);
//4.返回pre
代码
public ListNode reverseKGroup(ListNode head, int k) {
// write code here
ListNode tail = head;
//1.递归终止条件
for (int i = 0; i < k; i++) {
if (tail == null) {
return head;
}
//tail继续往后移,经过一个for循环，tail就变成了下一个组的head了
tail = tail.next;
}
//2.每个子任务，即bm1的反转链表
ListNode pre = null;
ListNode cur = head;
for (int i = 0; i < k; i++) {
if (cur != tail) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
}
//3.递归调用，将head串起来
head.next = reverseKGroup(tail, k);
return pre;
}
bm4
核心点
//1.首先定义一个dummy的虚拟头节点，这个不动，最终返回next
//2.定义一个res, res=dummy, res用来进行移动
//3.for循环将2个链表串起来
//4.长度不一样的，最后剩下的拼在res之后
主要是注意res的移动速度是慢于list1和list2的移动的
比如有个
ListNode dummy =new ListNode(-1);
ListNode res =dummy;
list1为1，3，5
list2为2，4，6
通过第一轮比较，dummy为 -1，1，3，5， list1=3,5, list2=2,4,6, res = 1,3,5
通过res串起来2个链表的
image.png
代码
public static ListNode Merge(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(-1);
ListNode res = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
res.next = list1;
list1 = list1.next;
res = res.next;
System.out.println("list1");
} else {
res.next = list2;
list2 = list2.next;
res = res.next;
System.out.println("list2");
}
}
if (list1 != null) {
res.next = list1;
}
if (list2 != null) {
res.next = list2;
}
return dummy.next;
}
bm5
核心点
合并k个，如果k=2,则就是bm4，合并2个有序链表
如果k>2，则就回到了分治，类似于二分法，将k个有序链表，拆成一个个子的集合，然后拆到每个子集合只有一个listNode，就可以每2个链表进行合并，一直往上合
比如有个链表，有5个元素，看下图最后一行，将链表拆成了5个ListNode,分成了5组
然后第一组先和第2组合并为，1->2->3，然后再和第3组合并为1-2>->2->3->4->5
然后第4组和第5组合并为3->5->6->7
然后剩下的组合并为最终的结果 1->2->2->3->4->5->5->6->7
分治的退出条件是left==right,即，链表的所有元素拆分成了一个个子元素，比如k=5，最终拆分成5组
2个listnode合并可以用bm4的代码
image.png
代码
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists.size() == 1) {
return lists.get(0);
}
//写一个新的divide方法，用于进行分治处理
return divideMerge(lists, 0, lists.size() - 1);
}
public ListNode divideMerge(ArrayList<ListNode> lists, int left, int right) {
//异常边界条件
if (left > right) {
return null;
} else if (left == right) {
//分治治理拆分的退出条件,left=right，即没法再拆分了，已经拆到ArrayList每一个元素了
return lists.get(left);
}
//分治的mid条件，将链表拆分为左右2部分，继续做拆分
int mid = (left + right) / 2;
ListNode listNodeLeft = divideMerge(lists, left, mid);
ListNode listNodeRight = divideMerge(lists, mid + 1, right);
//拆到不能再拆了，就可以每2组进行合并了
return merge(listNodeLeft, listNodeRight);
}
public ListNode merge(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(-1);
ListNode res = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
res.next = list1;
list1 = list1.next;
res = res.next;
} else {
res.next = list2;
list2 = list2.next;
res = res.next;
}
}
if (list1 != null) {
res.next = list1;
}
if (list2 != null) {
res.next = list2;
}
return dummy.next;
}
bm6
判断链表中是否有环，简单，快慢指针
https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
核心点
双指针问题，快慢指针
fast指针一定是比slow跑的快的，边界条件要以fast为准
代码
public static boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
//fast每次走2步，要注意npe问题
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
bm7
核心点
承接上一题，链表中有环的话，返回环的入口节点，快慢指针是再4相遇，但是入口是3，需要返回入口节点3
这个里面有1个数学原理，快慢指针相遇之后，快指针设置为head，然后每次移动一步，慢指针也移动一步，最终再次相遇的点，就是环的入口
image.png
代码
public ListNode entryNodeOfLoop(ListNode pHead) {
if (pHead == null) {
return null;
}
ListNode slow = hasCycle(pHead);
if (slow == null) {
return null;
}
ListNode fast = pHead;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
public ListNode hasCycle(ListNode pHead) {
if (pHead == null) {
return null;
}
ListNode slow = pHead;
ListNode fast = pHead;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
return slow;
}
}
return null;
}
bm8
核心点
可以先遍历链表，获得链表的size，然后再遍历一遍，到最后k个节点停止
也可以采用双指针做，快慢指针，快指针先走k步，然后快慢指针同时走，fast指向null的时候，fast指针遍历完了链表，而慢指针刚好走到了倒数第k个节点处
代码
if (pHead == null) {
return null;
}
ListNode fast = pHead;
ListNode slow = pHead;
//fast先走k步，剩下的步数就是size-k
for (int i = 0; i < k; i++) {
if(fast==null) {
//边界条件，返回不存在的元素，直接返回null
return null;
}
fast = fast.next;
}
//fast走完了整个链表，而slow刚走完size-k，最后slow停止了倒数第k个节点处
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
bm9
核心点
上一题是找到倒数第k个，这一题是要删除，并且返回删除后的链表，定义一个虚拟头节点，dummy，然后返回dummy.next
代码
public static ListNode removeNthFromEnd(ListNode head, int n) {
//边界条件
if (head == null) {
return null;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
for (int i = 0; i < n + 1; i++) {
if (fast == null) {
//删除不存在的节点，返回head
return head;
}
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
bm10
核心点
采用双指针，2个指针每次前进1步，每个指针将2个链表都遍历一次，那么2个指针遍历的长度是一样长的，则相遇的时候要返回的值
代码
if (pHead1 == null || pHead2 == null) {
return null;
}
//定义双指针
ListNode list1 = pHead1;
ListNode list2 = pHead2;
//每个指针各遍历完2个链表，因为2个指针遍历的长度一样长
//那么遍历完之后最终是在公共处结尾，那么往前找，第一次相等的地方就是返回值
while (list1 != list2) {
list1 = list1 == null ? pHead2 : list1.next;
list2 = list2 == null ? pHead1 : list2.next;
}
return list1;
bm11
核心点
2个长度不对等的链表相加，因为加法是从后往前加的，且涉及进位，可以先将2个链表使用反转链表的方式，先反转，然后再加起来，然后再将结果再反转返回
另一种是使用栈，题目限制空间复杂度O(n),时间复杂度O(n),利用栈先进先出的特点，把链表底部元素放到栈顶，然后出栈相加，加完之后构造一个新的返回值链表
代码
public static ListNode addInList(ListNode head1, ListNode head2) {
//边界条件，2个都为空，没有加的必要
if (head1 == null || head2 == null) {
return null;
}
//相加，遍历链表，使用栈的出栈入栈，可以比较方便的从后面开始加
//遍历链表，链表的开头在栈的最底下，链表的结尾元素在栈的最上方
Stack<Integer> stack1 = push(head1);
Stack<Integer> stack2 = push(head2);
//定义进位，根据方法描述，2个链表元素范围在0-9
// 那么最大是9+9+1=18，每次相加最多会进1位
int carry = 0;
//类似于反转链表，从后往前挪
ListNode newNode;
ListNode after = null;
//循环条件是2个栈有1个不为空，或者是进位不为空
//按照题目的示例，加到最后是9+1=10，会再进一位
while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
//出栈开始相加
int pop1 = stack1.isEmpty() ? 0 : stack1.pop();
int pop2 = stack2.isEmpty() ? 0 : stack2.pop();
//注意，这里还要加上进位
int temp = pop1 + pop2 + carry;
//进位需要拿10取余，最大是9+9+1=19，19/10=1
carry = temp / 10;
//尾数需要是拿10取模，11%10 =1, 1%10=1
temp = temp % 10;
//这里新的链表的尾节点就构造出来了
newNode = new ListNode(temp);
//这里把新的节点的next往after指，如果是第1轮，则next=null
newNode.next = after;
//after设置为新链表的node，再下一轮，往after指，就可以串成一个新的链表了
after = newNode;
}
return after;
}
/**
* 往栈里push数据
*
* @param head head
* @return stack
*/
public static Stack<Integer> push(ListNode head) {
Stack<Integer> stack = new Stack<Integer>();
while (head != null) {
stack.push(head.val);
head = head.next;
}
return stack;
}
bm12
核心点
单链表，没有size,不知道前后，所有有点排序有点难搞
实现思路可以参考合并k个有序链表，那一题的分治，是分到arrayList的每一个元素就结束
单链表这题，可以把链表拆分，拆成head-mid mid-right2个部分，一个个往下拆，直到最后拆的只有每一个元素了
比如链表1->3，拆成1->null,3->null，这样再把1，3这2个listnode使用合并2个有序链表，往上合
代码
public static ListNode sortInList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
//快慢指针
ListNode left = head;
//mid用来处理边界问题
ListNode mid = head.next;
ListNode right = head.next.next;
while (right != null && right.next != null) {
left = left.next;
mid = mid.next;
right = right.next.next;
}
//结束循环left已经在中间了
left.next = null;
return Merge(sortInList(head), sortInList(mid));
}
public static ListNode Merge(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(-1);
ListNode res = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
res.next = list1;
list1 = list1.next;
res = res.next;
System.out.println("list1");
} else {
res.next = list2;
list2 = list2.next;
res = res.next;
System.out.println("list2");
}
}
if (list1 != null) {
res.next = list1;
}
if (list2 != null) {
res.next = list2;
}
return dummy.next;
}
bm13
核心点
回文就是一个左右对称的结构，1，2，2，1是一个回文结构
由于链表不支持从后往前遍历，想到之前做的反转链表的题，可以把后半部分反转，那么反转后半部分就是1，2，然后head开始比较，后半部分反转完的遍历与前半部分进行比较
代码
public static boolean isPail(ListNode head) {
// write code here
if (head == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
//循环结束slow指针跑到了右半部分
//反转后半部分链表
slow = reverse(slow);
//fast重新回到head
fast = head;
while (slow != null) {
if (slow.val != fast.val) {
return false;
}
fast = fast.next;
slow = slow.next;
}
return true;
}
public static ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
bm14
核心点
给一个类似，1，2，3，4，5，6的链表，重排之后变成了1，3，5，2，4，6这种格式，index为基数的放到了一起，index为偶数的放到了一起，然后把奇偶串到一起，需要定义2个指针，然后往下下个指
代码
public static ListNode oddEvenList(ListNode head) {
// write code here
if (head == null) {
return head;
}
//链表为1,2,3,4,5,6
//奇数的指针,1
ListNode j = head;
//偶数的指针,2
ListNode o = head.next;
//衔接点的指针,2
ListNode xj = head.next;
while (o != null && o.next != null) {
//1->3，此时head因为j.next变化，head变成了1,3,4,5,6
j.next = o.next;
//1变成3
j = j.next;
//2->4,此时因为o.next发生了变化,o变成了2,4,5,6
o.next = j.next;
o = o.next;
}
//奇偶衔接到一起
j.next = xj;
return head;
}
bm15，删除链表中的重复元素，简单
核心点
这道题比较简单，一个有序的单链表，遍历，当前节点和next节点比较即可，如果cur.val=cur.next.val，则cur.next=cur.next.next
代码
public ListNode deleteDuplicates(ListNode head) {
// write code here
if (head == null || head.next == null) {
return head;
}
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
bm16
删除有序链表中重复的元素-II，mid
https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024?tpId=295&tqId=663&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
核心点
这道题相比第上一道题，有一个难点就是要删光所有的重复元素，而上一题可以保留一个，只要指针一直往后移就行了。
这题需要先拿到第一个相等的值，然后再拿这个相等的值做二次遍历，最终cur指针指向的是不和当前值相等的，最终会把所有的重复元素删掉
代码
public static ListNode deleteDuplicates(ListNode head) {
if (head == null && head.next == null) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = dummy;
//外层循环退出条件，由最深的嵌套决定
while (cur.next != null && cur.next.next != null) {
//cur是从dummy开始的，所以遍历的时候是从cur.next开始的
//比如head为1，1，1，2，3，加上dummy就变成了-1,1,1,1,2,3
if (cur.next.val == cur.next.next.val) {
//题目是要删掉所有的重复元素， 不保留，像上一题那样找到一个就指针后移，是不行的
//需要进行2层循环
int temp = cur.next.val;
//内层循环，把所有值为temp的都滤了一遍
//循环退出的时候，cur.next=2,
while (cur.next.val == temp) {
cur.next = cur.next.next;
}
} else {
//前一个和后一个值无关联，就把cur往后移
cur = cur.next;
}
}
return dummy.next;
}
