首页 > 试题广场 >

以组为单位翻转单向链表

[编程题]以组为单位翻转单向链表
  • 热度指数：1378 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

给一个单向链表以及整数N，使得每N个元素为一组进行翻转。要求时间复杂度O(n), 空间复杂度O(1)。

示例1

输入

{1,2,3,4,5,6,7,8},3

输出

{3,2,1,6,5,4,8,7}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
zzhxufeng头像 zzhxufeng 
/*
    迭代版本, 维护两个指针, 分别指向待反转了的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;
    }
}

发表于 2021-03-20 19:21:32 回复(0)
Java
洪泽凯头像 洪泽凯 
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;
    }
}

发表于 2021-03-16 21:09:39 回复(2)
煎饼果子w头像 煎饼果子w
头插法翻转节点法 
注意：n<=1可以直接返回，不需要翻转 

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 (n <= 1) {
            return head;
        }

        // write code here
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode p = newHead, q, post, rear;

        while (p.next != null) {
            q = p.next;
            rear = p.next;
            p.next = null;

            int k = 0;
            while (q != null && k < n) {
                post = q.next;
                q.next = p.next;
                p.next = q;
                q = post;
                ++k;
            }
            rear.next = q;
            p = rear;
        }

        return newHead.next;
    }
}


发表于 2021-03-26 21:19:27 回复(0)
wonderson头像 wonderson
三步：
1）根据当前区域头结点，找到当前翻转区域的最后一个节点；
2）将最后2一个节点的后面断链；
3）翻转这个区域，重新连上。 
import java.util.*;

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

public class Solution {
    public ListNode reverseLinkedList (ListNode head, int n) {
        if (n == 1) {
            //保证翻转1个以上
            return head;
        }
        ListNode res = new ListNode(0), result = res;
        res.next = head;
        ListNode pre, post;

        while (head != null) {
            pre = findNextHead(head, n);
            post = pre.next;
            pre.next = null;

            //翻转当前这段
            pre = reverse(head);
            res.next = pre;
            
            head.next = post;
            res = head;
            head = head.next;
        }

        return result.next;
    }
    
    //翻转链表
    private ListNode reverse(ListNode head) {
        ListNode pre = null, post = head;
        while (post != null) {
            ListNode tmp = post.next;
            post.next = pre;
            pre = post;
            post = tmp;
        }
        return pre;
    }

    //找到下一截翻转起点 //并与前一段切断
    private ListNode findNextHead(ListNode head, int k) {
        ListNode pre = null;

        while (head != null && k > 0) {
            pre = head;
            head = head.next;
            k--;
        }
        return pre;
    }

}

发表于 2022-03-28 10:10:29 回复(0)
fizzfrank头像 fizzfrank 
这道题其实不难，只是开始时，要反转两个链表，后面每次循环反转一个链表，为了屏蔽差异，引入头节点，这是链表操作常用的技巧。

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;
    }

发表于 2021-07-17 22:16:59 回复(0)
--千本樱头像 --千本樱 
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

发表于 2021-07-14 15:11:11 回复(0)
aliang_keep_up头像 aliang_keep_up
C++
只需要在翻转每个节点数量为K的子链表后将上一个翻转完成的子链表的尾巴接到这个翻转完成的子链表的头。
简单起见用了个queue，也可以不用，在循环内部操作一下也行。 
class Solution {
public:
    /**
     * reverse the given linked list
     * @param head ListNode类 the head of the linked list
     * @param n int整型 the N
     * @return ListNode类
     */
    ListNode* reverseLinkedList(ListNode* head, int n) {
        // write code here
        ListNode* tmp = head;
        ListNode* next_ = new ListNode(0);
        ListNode* prev = nullptr;
        ListNode* node = new ListNode(0);
        queue<ListNode*> q;
        while (tmp) {
            node = tmp;
            for (int i = 0; i < n && tmp != nullptr; i++) {
                next_ = tmp->next;
                tmp->next = prev;
                prev = tmp;
                tmp = next_;
            }
            q.push(prev);
            q.push(node);
            prev = nullptr;
        }
        ListNode* ans = q.front();
        while (!q.empty())
        {
            q.pop();
            ListNode* a = q.front();
            q.pop();
            a->next = q.front();
        }
        return ans;
    }
};


发表于 2021-07-12 17:34:32 回复(0)
HikawaRin头像 HikawaRin

本题是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

发表于 2021-06-30 21:02:35 回复(0)
_奶酪头像 _奶酪 
/*
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
发表于 2021-05-05 16:46:39 回复(0)
卡瓦夏日头像 卡瓦夏日 
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

发表于 2021-04-20 16:09:46 回复(0)
xxxshox头像 xxxshox
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||head.next==null) return head;
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode cur=dummy;
        int i=0;
        while(cur.next!=null&&cur.next.next!=null){
            ListNode cur1=cur.next.next;
            ListNode pre=cur.next;
            while(i<n-1&&cur1!=null){
                ListNode temp=cur1.next;
                cur1.next=pre;
                pre=cur1;
                cur1=temp;
                i++;
            }
            ListNode temp=cur.next;
            cur.next.next=cur1;
            cur.next=pre;
            cur=temp;
            i=0;
        }
        return dummy.next;
    }
}
发表于 2021-04-11 19:07:43 回复(0)
C/C++
拧螺丝的马里奥头像 拧螺丝的马里奥
递归超内存。 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

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

class Solution {
public:
    /**
     * reverse the given linked list
     * @param head ListNode类 the head of the linked list
     * @param n int整型 the N
     * @return ListNode类
     */
    ListNode* reverseLinkedList(ListNode* head, int n) {
        // write code here
        if(n <= 1) return head;
        ListNode* tmp = head;
        ListNode* pre = head;
        for(int i = 0; i < n; i++){
            if(tmp == nullptr) break;
            tmp = tmp->next;
        }

        ListNode* newHead = reverse(head, tmp);
        head->next = reverseLinkedList(tmp, n);
        return newHead;

    }

    ListNode* reverse(ListNode* a, ListNode* b) {
        ListNode* pre, *cur, *next;
        pre = nullptr;
        cur = a;
        next = b;
        while(cur != nullptr && cur != b) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

改用迭代，pass all cases。反转链表的几种变体
1. 反转全部
2. 反转前n个
3.反转[m, n] 
4.每k个节点反转 

class Solution {
public:
    /**
     * reverse the given linked list
     * @param head ListNode类 the head of the linked list
     * @param n int整型 the N
     * @return ListNode类
     */
    ListNode* reverseLinkedList(ListNode* head, int n) {
        // write code here
        if(n <= 1) return head;
        ListNode* tmp = head;
        ListNode* pre = head;
        int len = 1;
        for(int i = 0; i < n; i++){
            if(tmp == nullptr) break;
            tmp = tmp->next;
            len++;
        }
        
        auto reverse = [](ListNode* a, ListNode* b) -> ListNode* 
        {
            ListNode* pre, *cur, *next;
            pre = nullptr;
            cur = a;
            next = b;
            while(cur != nullptr && cur != b) {
                next = cur->next;
                cur->next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        };
        ListNode* newHead = reverse(head, tmp);
        if(len <= n) { //如果长度<=n只需要反转一次
            return newHead;
        }
        
        //题目不让递归，那就迭代咯
        ListNode* curTail = head;    //迭代时，记录每次反转后的尾节点
        while(tmp != nullptr) {        // 用于连接下一个反转子链表的头节点
            head = tmp;
            for(int i = 0; i < n; i++) {
                if(tmp == nullptr) break;
                tmp = tmp->next;
            }
            curTail->next = reverse(head, tmp);
            curTail = head;
        }
        return newHead;
    }
};


编辑于 2021-03-30 22:25:41 回复(1)
付峻玲头像 付峻玲
js
let arr = [1,2,3,4,5,6,6,7]
    let newArr
    function flip(arr, num) {
        if(arr.length < num) {
            return arr.reverse()
        }else {
            newArr = arr.slice(0,3).reverse()
        }
        return newArr.concat(flip(arr.slice(3) ,num))
    }
    console.log(flip(arr, 3))

发表于 2021-03-26 15:33:25 回复(0)
不偷不抢安度因_头像 不偷不抢安度因_ 
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;
         
    }
};

发表于 2021-03-22 22:09:11 回复(0)
雷诺诺头像 雷诺诺 
用递归能很好解决。。就是翻转链表

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;

发表于 2021-03-18 00:21:24 回复(0)
C/C++
牛客213973843号头像 牛客213973843号
ListNode* reverseLinkedList(ListNode* head, intn) {
        if(head == nullptr)return nullptr;
        ListNode* a = head;
        ListNode* b = head;
        for(inti=0; i<n; i++){
            //if(b == nullptr)break;
            b = b->next;
        }
        ListNode* newhead = newreverse(a, b);
        a->next = reverseLinkedList(b, n);
        return newhead;
        // write code here
    }
private:
    ListNode* newreverse(ListNode* a, ListNode* b){
        ListNode* pre = nullptr;
        ListNode* cur = a;
        while(cur != b && cur != nullptr){
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
发表于 2021-03-09 21:39:03 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 测试开发工程师 深圳虾皮信息科技有限公司 大数据开发工程师 Java工程师
上传者：小小
难度：
16条回答 4201浏览

热门推荐

通过挑战的用户

相关试题

以组为单位翻转单向链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号