乐趣区

关于数据结构:20211220刷题笔记链表系列

链表有很多繁琐的中央。往往再一些细节上的解决,是很重要的,当然,链表我集体认为是最看重细节的中央,然而链表如果说可能一步步理分明细节,实际上是能够写进去的。

从一到最简略的反转链表开始做起
剑指 Offer 24. 反转链表

毫无疑问,咱们须要三个指针去反转
咱们再脑海中设想一条链表
help->1->2->3->4->5->NULL
这个时候 脑海中将 1 指向 help,而后呢?咱们是不是须要提前保留 2 的值,因为咱们将 1 指向 help 的时候曾经没有 2 的援用了,所以再 1 指向 help 之前,咱们先保留下 2 的援用,始终反复这个过程,直到什么时候?是不是直到最初一个节点无奈指向前一个节点的时候,很显然,断定条件就是 cur!=null

ListNode pre = new ListNode(-1),help = pre,pre.next=head,cur = head,next;

while(cur!=null){
    next = cur.next;
    cur.next = pre;
    pre= cur;
    cur = next;
}
return help.next;

这是一种办法。还有没有其余的办法?
help->1->2->3->4->5->NULL
同样是这条链表。
如果咱们将节点 2 摘下来,插入 help->1 之间 是不是实现了部分的反转,始终反复这个过程,是不是就是实现了链表的反转?
当初想,如何实现这个过程?

ListNode pre = new ListNode(-1),next;
pre.next=head;
while(head.next!=null){
    next = head.next;
    head.next = next.next;
    next.next = pre.next;
    pre.next = next;
}
return pre.next;

进阶一点呢?
25. K 个一组翻转链表
区间内反转,这里只将第二种反转,反转完了之后是不是以后区间的 head 节点成为下一个区间的 pre 节点?下一个 cur 节点是不是以后 cur 节点的 next 节点?

ListNode pre = new ListNode(-1),help = pre,countNode = head,next;
pre.next = head ;
int count = 0;
while(countNode!=null){
    count++;
    countNode = countNode.next;
}
for(int i =0;i<count/k;i++){for(int j= o;j<k-1;j++){
        next = head.next;
        head.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    pre= head;
    head = head.next;
}
return help.next;
退出移动版