以组为单位翻转单向链表

[编程题]以组为单位翻转单向链表

热度指数：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，点此查看相关信息

算法知识视频讲解

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)