以组为单位翻转单向链表

/*
    迭代版本, 维护两个指针, 分别指向待反转了的head和tail.
*/

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * reverse the given linked list
     * @param head ListNode类 the head of the linked list
     * @param n int整型 the N
     * @return ListNode类
     */
    public ListNode reverseLinkedList (ListNode head, int n) {
        // write code here
        if(head == null) return null;
        if(head.next == null || n <= 1) return head;
        
        ListNode nHead = head, nTail = head;
        ListNode prev = null;
        boolean flag = true;
        while(nHead != null){
            int t = 1;
            while(t < n && nTail.next != null){
                nHead = insertInHead(prev, nHead, nTail);
                t ++;
            }
            if(flag){
                flag = false;
                head = nHead;
            }
            nHead = nTail.next;
            prev = nTail;
            nTail = nHead;
        }
        return head;
    }
    
    static ListNode insertInHead(ListNode prev, ListNode head, ListNode tail){
        if(tail == null)    return head;
        if(head == null)    return null;
        ListNode next = tail.next;
        tail.next = next.next;
        next.next = head;
        if(prev != null){
            prev.next = next;
        }
        
        return next;
    }
}

public class Solution {
    /**
     * reverse the given linked list
     * @param head ListNode类 the head of the linked list
     * @param n int整型 the N
     * @return ListNode类
     */
    public ListNode reverseLinkedList (ListNode head, int n) {
        if(head == null) return null;
        ListNode a = head;
        ListNode b = head;
        for(int i = 0; i < n; i++){
            if(b == null) break;
            b = b.next;
        }
        ListNode newHead = newReverse(a,b);
        a.next = reverseLinkedList(b,n);
        return newHead;
    }
    //可以参考LeetCOde反转链表,多一个条件:当前节点不为尾节点b
    public ListNode newReverse(ListNode a, ListNode b){
        ListNode pre = null;
        ListNode cur = a;
        while(cur != null && cur != b){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

这道题其实不难，只是开始时，要反转两个链表，后面每次循环反转一个链表，为了屏蔽差异，引入头节点，这是链表操作常用的技巧。

public ListNode reverseLinkedList(ListNode head, int n) {
        // write code here
        ListNode start = new ListNode(0);
        ListNode cur;
        ListNode next;
        ListNode pre = null;
        ListNode tail = start;
        cur = head;
        int count = 0;

        while (cur != null) {
            ListNode tmp = cur;
            count = 0;
            while (cur != null && count < n) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
                count++;
            }

            tail.next = pre;
            tail = tmp;
            pre = null;
        }

        return start.next;
    }

class Solution:
    def reverseLinkedList(self , head , n ):
        if not head:
            return 
        if not head.next&nbs***bsp;n == 1:
            return head

        # 标记是否为第一组，需要确定新的head
        flag = True
        
        res_head = head
        tail = head

        while head:
            # 先判断是否还剩下一组k个结点的链表
            test = head
            # 记录剩余不足k个结点的链表长度
            last = 0
            for i in range(n):
                if not test:
                    break
                last += 1
                test = test.next    
            # 直接翻转后面剩余结点的个数
            cnt = last - 1
            cur_head = head
            while cnt:
                cnt -= 1
                new_head = head.next
                head.next = head.next.next
                new_head.next = cur_head
                cur_head = new_head
            
            # 第一组之后的每一组都要更新上一组的末尾结点指向当前这一组的cur_head
            if not flag:
                tail.next = cur_head
            else:
                # 如果这是第一组，更新并记录新的res_head
                res_head = cur_head
                flag = False
            # 这一组的末尾结点就是当前的head
            tail = head
            # 进入下一组的翻转
            head = head.next
        
        return res_head

本题是LeetCode 25. Reverse Nodes in k-Group的简化版本(反转前无需判断最后是否剩余K个节点)
用递归的方法来解相对好记, 但会占用更多内存
具体解法如下

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

class Solution {
public:
    ListNode* reverseLinkedList(ListNode* head, int n) {
        // 一个链表头部增加/减少 n 个元素后适用同样的方法
        // 给出终止条件 1. 空链表 2. 仅有头部节点 3. 组内元素个数小于1(无需翻转)
        if (head == nullptr || head->next == nullptr || n<=1){ return head; }

        ListNode *pit = head, *it = head->next, *nit;
        int step = n-1; // it 从第二个节点开始
        // 逐个翻转结点
        while (step && it != nullptr){
            nit = it->next; it->next = pit; pit = it; it = nit;
            --step;
        }
        // 终止时 it 经过 n 个节点 恰好为下一组的起点
        // head 成为新的尾部连接翻转后的头部
        // pit 成为新的头部直接返回
        head->next = reverseLinkedList(it, n);
        return pit;
    }
};

总体时间复杂度 O(N), 空间复杂度 O(1)
本题运行时间： 8 ms 占用内存：536K

/*
1. 特判head为空和n=1的情况
2. 记录上一组翻转后的尾部lastTail和当前组翻转后的头部nowHead和尾部nowTail，当组数>=2时，将lastTail和nowHead链接
3. head标记链接对<head, p>中的前一个元素，p->next=head
*/
ListNode* reverseLinkedList(ListNode* head, int n) {
    ListNode *p, *nowTail, *p_next, *nowHead, *lastTail, *ans;
    bool f = false;
    if(head==NULL || n==1 ) return head;
    while(1)
    {
        int cnt = 0;
        p = head->next;
        nowHead = nowTail = head; //翻转前的起始位置是翻转后的尾
        // head p p_next  链接对<head, p>,
        //  1   2   3
        //  2   3   4
        while(p!=NULL) {
            p_next = p->next;
            p->next = head; // head<-p
            cnt++;
            nowHead = head = p;
            p = p_next;
            if(cnt==n-1) {
                head = p_next; // 此段结束，下一段的第一个链接对
                break;
            }
        }
        if(f) lastTail->next = nowHead; // 段数>=2时，段和段之间进行链接
        if(!f) {
            f = true;
            ans = nowHead; // 翻转后的头部是第一段的头部
        }
        lastTail = nowTail; // 翻转之后当前段的尾，即将于下一段翻转后的头相连
        if(p==NULL) {
            nowTail->next = NULL; //结束前将尾部的next置为NULL
            break;
        }
    }
    return ans;
}


没有特判传入的链表为空的情况，段错误了好久了QAQ

class Solution:
    def reverseLinkedList(self , head , n ):
        i,j=0,0       
        pre=None
        cur=head
        t0=head
        while cur:
            temp=cur.next 
            if n==1:
                return head
            if i==0:
                t=cur
            if i==n-1:
                cur.next=pre 
                if j==0:
                    newh=cur
                    j=1
                else:
                    t0.next=cur
                    t0=t
                pre=None
                cur=temp
                i=0
                continue
            cur.next=pre 
            pre=cur
            cur=temp
            i+=1
        if j==0:
            newh=pre
        elif i!=0:
            t0.next=pre
        return newh

class Solution {
public:
    ListNode* reverseLinkedList(ListNode* head, int n) {
        if (!head || !head->next) {
            return head;
        }
        int len = 0;
        ListNode* p = head;
        while (p) {
            ++len;
            p = p->next;
        }
        int loop = len / n;
        if (len % n) {
            loop++;
        }
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        p = head;
        ListNode* pnext = p->next;
        while (loop--) {
            //p->next = NULL;
            if (!loop) {
                n = (len % n) ? len % n : n;
            }
            for (int i = 0; i < n - 1; ++i) {
                ListNode* tmp = pnext->next;
                pnext->next = pre->next;
                pre->next = pnext;
                pnext = tmp;
            }
 
            pre = p;
            p->next = pnext;
            p = pnext;
            if (!pnext) {
                break;
            }
            pnext = pnext->next;
        }
         
        head = dummy->next;
        delete dummy;
        return head;
         
    }
};

用递归能很好解决。。就是翻转链表

if(head==NULL) return head;
ListNode* q=head;
ListNode* p=head->next;
for(int i=0;i<n-1&&p!=NULL;i++){
    q->next=p->next;
    p->next=head;
    head=p;
    p=q->next;
}
q->next=reverseLinkedList(p, n);
return head;