问题1
如何把一个链表反转过来,例如1->2->3->4 反转为4->3->2->1 ?
原理
可以重写定义一个头结点,然后采用头插的方式把老的链表插入到新的链表里,头插法如何实现可以参考:头插法
代码
class Solution {
public ListNode reverseList(ListNode head) {
ListNode newHead = new ListNode(-1);
ListNode run = newHead;
while (head!=null){
ListNode cur = head;
head = head.next;
cur.next = run.next;
run.next = cur;
}
return newHead.next;
}
}
注意事项
在做头插的时候要注意节点移动的时候,ListNode cur = head; head = head.next; 不要让老的链表断开。
问题2
如何旋转链表的m->n中间节点旋转过来,例如1->2->3->4 反转2到3为 1->3->2->4
原理
- 首先,找到第m个节点的前一个节点记录下来,第m个节点也要保存下来,这个记录为第一部分节点。
- 其次,用头插法把m到n之间的节点反转,记录为第二部分节点,剩余的节点为第三部分节点。
- 最后,把第一部分节点和第二部分节点连起来,同时把第m个节点和剩余的第三部分节点连接起来。
代码
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head==null){
return head;
}
// find first
ListNode newHead = new ListNode(-1);
ListNode run = newHead;
for(int i=1;i<m;i++){
run.next = head;
head = head.next;
run = run.next;
}
// find second
ListNode dump = head;
ListNode reverseHead = new ListNode(-1);
ListNode reverseRun = reverseHead;
for(int i=m;i<=n;i++){
ListNode cur = head;
head = head.next;
cur.next = reverseRun.next;
reverseRun.next = cur;
}
//find third
run.next = reverseHead.next;
dump.next = head;
return newHead.next;
}
}
注意事项
- 在做头插法反转的时候需要注意的是:cur.next = run.next; run.next = cur; 核心代码
- 因为是反转部分代码,所以需要注意的是,记录下来第一个需要反转的位置,因为到时候它会变成第二部分的最后一个位置。
问题3
把一个长度为n的链表,按照长度为m的规则反转,注意的是n>=m>0
原理
- 首先,需要明确的是如何按照规则m反转,可以联想到使用stack来处理这个问题,stack是天然的先进后出的结构。
- 其次,在实现的时候每次获取m个元素存入栈中,然后依次把栈里的元素出栈,加入到新的链表里。在做加入stack之前把首节点dump下来。
- 最后,把剩余的部分元素加入到新的链表里,剩余部分的首节点,就是之前dump的节点。
代码
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head==null||k<=0){
return head;
}
ListNode newHead = new ListNode(-1);
ListNode run = newHead;
ListNode dump = null;
int count = k;
Stack<ListNode> stack = new Stack<>();
while(true){
dump = head;
while(head!=null&&count>0){
stack.add(head);
head = head.next;
count--;
}
if(count>0){
break;
}
while(!stack.isEmpty()){
ListNode cur = stack.pop();
run.next = cur;
run = run.next;
}
count = k;
}
run.next = dump;
return newHead.next;
}
}
注意事项
- m这个数需要记录下来,每次进出stack之后需要恢复m
- 每次在开始加入stack之前,需要dump下head节点,目的是剩余的节点追加到新的链表里,需要一个记录头结点
- 设计的是永真循环,退出的条件是count>0,说明链表遍历完了,但是剩余元素不满足m个。
网友评论