力扣25题（K 个一组翻转链表）_给你一个链表,每k个节点一组进行翻转

目录

题目：K 个一组翻转链表

解题思路：

 总代码为：

---

题目：K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

解题思路：

1.因为题中对k有要求，如果节点总数不是 k 的整数倍，则保持原有顺序，所以还需要判断节点数     是否比k大

2.因为题中说每 k 个节点一组进行翻转，所以首先应该找出这一组节点的头节点和尾节点

3.最后将这组数据进行翻转，翻转后接入初始链表中

---

首先判断链表节点个数：

有三种情况 1：链表节点数为0，即链表没有节点

2：链表节点数<k,此时不需要进行翻转

3：链表节点数>k,此时需要翻转

当处于情况1或者2时，则直接返回该链表，即return newHead.next

因此首先应该创建一个头节点head的前驱节点newHead:方便输出链表

（不用头节点head输出链表因为怕该链表为空）

这时还需要创建一个代替newHead的节点prev：用来代替newHead来遍历链表，使newHead始终位置保持不变，方便输出链表

---

下面画图解释情况3：（假设链表有5个节点）

此时链表节点数>k,需要翻转，因此首先应该找出这一组节点的头节点和尾节点

头节点为head，还需要创建一个尾节点tail

                 

 

 此时需要让tail节点找到所需要翻转的k个节点的尾部（假设k为3）

 

 此时就可以进行翻转了~翻转之后再接入原来的链表中即可

重点：由于翻转之后还要接入原来的链表中，因此我们需要知道tail的后一个节点，所以还需要创               建tail的后一个节点tailNext

当然在进行翻转之前，我们需要清楚需要翻转的部分，即head~tail之间的节点

为了防止头节点head被移动，还需创建一个节点p代替head

重点：进行翻转的过程中需要记录p的下一个节点，因此还需要创建一个节点pNext(防止1节点翻转到后面时找不到2节点，因为此时p.next已经指向4节点)

 

 

 

 代码为：

 翻转之后，只需要将翻转之后的链表插入原来的链表即可

 

然后循环遍历寻找k个节点进行翻转即可（直到head为空）

 总代码为：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode prev = newHead;
        ListNode tail = prev;
        while(head!=null){
            for(int i = 0;i < k;i++){
                tail = tail.next;
                if(tail == null){
                    return newHead.next;
                }
            }
            ListNode[] reverse = myReverse(head,tail);
 
            head = reverse[0];
            tail = reverse[1];
            prev.next = head;
            prev = tail;
            head = tail.next;
        }
        return newHead.next;
    }
    public static ListNode[] myReverse(ListNode head,ListNode tail){
        ListNode tailNext = tail.next;
        ListNode p = head;
        while(tailNext != tail){
            ListNode pNext = p.next;
            p.next = tailNext;
            tailNext = p;
            p = pNext;
        }
        return new ListNode[]{tail,head};
    }
}