【作业7】字节真题：变形的链表反转

这是之前面试字节遇到的一道算法题，大致描述如下：

给定一个单链表的头节点 head,实现一个调整单链表的函数，使得每K个节点之间为一组进行逆序，并且从链表的尾部开始组起，头部剩余节点数量不够一组的不需要逆序。（不能使用队列或者栈作为辅助）

例如：
链表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8，3->4->5，1->2各位一组。调整后：1->2->5->4->3->8->7->6->null。其中 1，2不调整，因为不够一组。

作业要求：

1、给出运行通过的代码，自己测试数据。
1、为了统一格式，为下面定义了一个方法

ListNode reverseKGroup2(ListNode head, int k){

}

请打卡给出你的代码。

答案：自己先做，之后在看答案：记一道字节跳动面试：变形的链表反转

PS：如果你不知道怎么打卡，可以看这里：打卡细则

shuaidi

更新于 4 年前 310 14

共以下 14 个回答

幽小皮永久会员 2024年4月12日下午8:54
“`
//首先逆序然后使用链表反转
public ListNode reverseKGroup(ListNode head, int k) {
```
    ListNode newhead = reverseIn(head);
    ListNode nnhead = reverse(newhead, k);
    return reverseIn(nnhead);

}```java
```
0 赞同 0 条回复

登录以回复

开心果🍅 永久会员 2024年3月31日下午8:53

““java
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
/*

    //  1 2 3 4 5  ---》 5 4 3 2 1  然后从头开始 分组逆转   4 5 2 3 1  ---- 》再去反转   1 3 2 5 4
    //  1 3 2 5 4ok！*/
    ListNode rev1 = reverseList(head);
    //寻找当前分割的节点
    ListNode temp = head;
    if(int i =1 ;i<k && temp!== null;i++){
        temp = temp.next;
    }
    if (temp == null) return  head;

    //把当前节点和下面的链表进行分割
    ListNode t = temp.next;
    temp.next = null;
    ListNode  newHead = reverseList(head);
    ListNode  newTemp = reverseKGroup(t,k);

    head.next = newHead;

    ListNode rev2 = reverseList(newHead);
    return  rev2;

}

ListNode reverseList(ListNode head) {
    if(head == null || head.next == null)
        return head;
    ListNode result = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return result;
}

}

0 赞同 0 条回复

泡芙永久会员 2023年9月5日下午10:31

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 调用逆序函数
        head = reverseList(head);
        // 调用每 k 个为一组的逆序函数（从头部开始组起）
        head = reverseKGroup2(head, k);
        // 在逆序一次
        head = reverseList(head);
        return head;
    }
    ListNode reverseKGroup2(ListNode head, int k) {

        // head->1->2->3->4->5  k=2
        ListNode temp = head; // 定位需要反转的最后一个节点
        for (int i = 1; temp != null && i < k; i ++) {
            temp = temp.next;
        }

        // 不足k个，不需要反转
        if (temp == null) {
            return head;
        }

        // 切分
        // head->1->2->null  t->3->4->5->null
        ListNode t = temp.next;
        temp.next = null;

        // 开始反转 newHead->2->1->null
        ListNode newHead = reverseList(head);
        // newTemp->3->4->5->null
        ListNode newTemp = reverseKGroup2(t, k);
        // 拼接
        head.next = newTemp;

        return newHead;

    }

    // 反转链表
    ListNode reverseList(ListNode head) {
        // 链表为空或只有一个节点
        if (head == null || head.next == null) {
            return head;
        }

        // 关系式
        ListNode res = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }


}

0 赞同 0 条回复

Thaddeus 永久会员 2023年9月1日下午6:07

打卡

class Solution {
public:
    //K个一组翻转链表，头部剩余
    ListNode* reverseKGroup2(ListNode* head, int k) {
        return reverseList(reverseKGroup(reverseList(head), k));
    }

    //K个一组翻转链表，尾部剩余
    ListNode* reverseKGroup(ListNode* head, int k) {       
        ListNode* tmp = head;
        for(int i = 1; tmp != nullptr && i < k; i++) {
            tmp = tmp->next;
        }

        if(tmp == nullptr) return head;
        ListNode* t = tmp->next;
        tmp->next = nullptr;
        ListNode* newHead = reverseList(head);
        head->next = reverseKGroup(t, k);
        return newHead;
    }

    //整体翻转链表
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;

        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

0 赞同 0 条回复

LicodeCO.LTDao 普通 2023年5月23日下午6:27

function reverseKGroup(head: any, k: number) {
  let temp = head;

  for (let i = 1; temp !== null && i < k; i++) {
    temp = temp.next;
  }

  if (temp === null) {
    return head;
  }

  let t = temp.next;
  temp.next = null;

  let newHead = reverseList(head);
  let newTemp = reverseKGroup(t, k);
  head.next = newTemp;
  return newHead;

  function reverseList(head: any) {
    if (head === null || head.next === null) {
      return head;
    }
    let newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
  }

  function reverseKGroup2(head: any, k: number) {
    // 整体反转
    head = reverseList(head);

    // 局部反转
    head = reverseKGroup(head, k);

    // 整体反转
    head = reverseList(head);
    return head;
  }
}

0 赞同 0 条回复

小趴菜永久会员 2023年5月17日下午3:13

class Solution {
public ListNode reverseKGroup(ListNode head,k){
ListNode firstReverse = reverseHead(head);
ListNode duringReverse = reverseKGroup(firstReverse,k);
ListNode lastReverse = reverseHead(duringReverse);
return lastReverse;
}
public ListNode reverseKGroup2(ListNode head, int k) {
//先分组
ListNode temp = head;
for(int i = 1;i<k&&temp!=null;i++){
temp = temp.next;
}
if(tempnull){
return head;
}
ListNode newTemp = temp.next;
temp.next = null;
ListNode newhead reverseHead(head);
ListNode lasthead reverseKGroup2(newTemp,k);
head.next = lasthead;
return newhead;
}
public ListNode reverseHead(ListNode head){
if(headnull||head.nextnull){
return head;
}
ListNode last = reverseHead(head.next);
head.next.next = head;
head.next = null;
return last;
}
}

1 赞同 0 条回复

登录以回复

Violet 永久会员 2023年5月9日下午1:26

一

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode temp = head;
        for (int i = 0; i < k - 1 && temp != null; i++) {
            temp = temp.next;
        }
        if (temp == null) {
            return head;
        }
        ListNode subhead = temp.next;
        temp.next = null;

        ListNode newhead1 = reverse(head);
        ListNode newhead2 = reverseKGroup(subhead, k);

        head.next = newhead2;
        return newhead1;

    }

    public ListNode reverse(ListNode head){
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newhead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newhead;
    }

    ListNode reverseKGroup2(ListNode head, int k){
        //reverse
        ListNode newhead = reverse(head);
        //reverseKGroup
        ListNode newhead2 = reverseKGroup(newhead, k);
        //reverse
        ListNode newhead3 = reverse(newhead2);
        return newhead3;
    }
}

0 赞同 0 条回复

庄重普通 2023年4月24日下午9:12

class Solution {
public:
    //  1, 2, 3, 4, 5    1, 3, 2, 5, 4
    ListNode* reverseKGroup(ListNode *head, int k) {
        // 1, 2, 3, 4, 5     5, 4, 3, 2, 1->null
        ListNode *pCur = reverse(head); 
        // 功能: 分组进行排序
        ListNode *p = recur(pCur, k);
        return p;
    }
    ListNode* recur(ListNode *head, int k) {

        ListNode *pCur = head;
        for(int i = 1; pCur != NULL && i < k; i ++) {
            pCur = pCur->next;
        }

        if(pCur == NULL) {
            return head;
        }
        // head->5, 4->null   pTmp->3, 2, 1->null k=2
        ListNode *pTmp = pCur->next;
        pCur->next = NULL;
        // p->1, 3, 2->null
        ListNode *p = recur(pTmp, k);
        ListNode *pp = p;
        while(pp->next != NULL) {
            pp = pp->next;
        }
        pp->next = head;

        return p;
    }

    ListNode* reverse(ListNode *head) {

        if(head == NULL || head->next == NULL) {
            return head;
        }

        ListNode *p = reverse(head->next);
        head->next->next = head;
        head->next = NULL;
        return p;
    }
};
// 时间复杂度O(2n);
// 空间复杂度O(n/k + n);

0 赞同 0 条回复

是梦终空永久会员 2023年4月18日上午11:51

时间O(n)

ListNode reverseKGroup2(ListNode head, int k){
            //本来直接递归，做了才发现最后一次的返回结果和前面的递归返回结果不同，不然无法返回头结点，
            //和k个一组翻转链表相似，就是得找到它从哪个节点开始，然后拼接
            ListNode temp = head;
            int len = 0;
            //求出链表长度
            while(temp != null){
                temp = temp.next;
                len++;
            }
            //算一下得从哪里开始反转
            int n = len%k;
            ListNode newTemp = new ListNode(0,head);
            ListNode list = new ListNode(0,head);
            list = newTemp;
            while(n-- > 0){
                list = list.next;
            }
            //拼接
            list.next = reverseKGroup2(list.next,k);
            //返回头结点
            return newTemp.next;
        }

        ListNode reverseKGroup(ListNode head, int k){
            ListNode temp = head;
            for(int i = 1; temp != null && i < k; i++ ){
                temp = temp.next;
            }  
            if(temp == null){
                return head;
            }
            ListNode t = temp.next;
            temp.next = null;
            ListNode newHead = reverseList(head);
            ListNode newTemp = reverseKGroup2(t, k);
            head.next = newTemp;
            return newHead;
        }
 public ListNode reverseList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

0 赞同 0 条回复

C++小将永久会员 2023年4月17日下午9:53

打卡

占个坑，一开始只想到了先用求余的方法找到反转起始点，没想到答案的解法这么优雅，过段时间来补卡！刚看完答案记得太清楚了/

1 赞同 0 条回复

登录以回复

秊永久会员 2023年4月17日上午11:34

这道题难点在于：将从头结点开始变为尾结点开始，如果还按照从头节点开始的思路，那么我们事先不知道应该从头结点往后第几个节点开始，进行一组一组的反转。
除了两次反转链表，我还有一个想法，就是先完整遍历一次链表，获取其长度 length，用 length % k，不就知道应该应该从头结点往后第几个节点开始了🤪
时间 $O(n)$
空间 $O(1)$

ps: 为了省事，可以直接在 Leetcode 上测试，只执行代码，不提交，看输出结果对就行😛

public ListNode reverseKGroup2(ListNode head, int k) {
        ListNode header = new ListNode(0, head);
        ListNode cur = header.next;

        // 获取长度
        int length = 0;
        while (cur != null) {
            cur = cur.next;
            ++length;
        }

        // 找到从哪开始反转
        int count = length % k;
        cur = header;
        while (0 != count--) {
            cur = cur.next;
        }

        // 拼接
        cur.next = reverseKGroup(cur.next, k);

        return header.next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (null == head) return null;
        ListNode header = new ListNode(0, head);
        ListNode fast = header, low = header;

        // 遍历到第一组要反转节点的最后一个节点，将其切断，并保存切断后的 tail
        int count = k;
        while (0 != count--) {
            fast = fast.next;
            // if (null == fast) return head;
        }
        ListNode tail = fast.next;
        fast.next = null;

        // 将第一组节点反转，保存反转后的最后一个节点
        ListNode tailNew = low.next;
        low.next = reverse(low.next);

        // 递归，用「反转后的最后一个节点」拼接新的反转后的链表
        tailNew.next = reverseKGroup(tail, k);

        return header.next;
    }

    // 反转链表
    private ListNode reverse(ListNode head) {
        ListNode last = null, pre = head;

        while (pre != null) {
            ListNode tmp = pre.next;
            pre.next = last;
            last = pre;
            pre = tmp;
        }

        return last;
    }

1 赞同 0 条回复

Everglow 永久会员 2023年4月15日下午1:16

public class LinkedList {

    public static void main(String[] args) {
        ListNode head = add(null, 1);
        add(head, 2);
        add(head, 3);
        add(head, 4);
        add(head, 5);
        add(head, 6);
        add(head, 7);
        add(head, 8);
        ListNode newHead = reverseKGroup2(head, 3);
        traverse(newHead);
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode add(ListNode head, int val) {
        if (head == null) {
            return new ListNode(val, null);
        }
        ListNode p = head;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new ListNode(val, null);
        return head;
    }

    public static void traverse(ListNode head) {
        if (head == null) {
            System.out.println("链表为空");
        }
        ListNode p = head;
        while (p != null) {
            System.out.println(p.val);
            p = p.next;
        }
    }

    static ListNode reverseKGroup2(ListNode head, int k){
        if(head == null || head.next == null) {
            return head;
        }
        ListNode reverse = reverse(head);
        return reverse(reverseByGroup(reverse, k));
    }

    static ListNode reverseByGroup(ListNode head, int k) {
        ListNode p = head;
        for (int i = 0; i < k - 1; i++) {
            p = p.next;
            if (p == null) {
                return head;
            }
        }
        ListNode nextGroup = p.next;
        p.next = null;
        ListNode newHead = reverse(head);
        head.next = reverseByGroup(nextGroup, k);
        return newHead;
    }

    static ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

}

0 赞同 0 条回复

小肸永久会员 2023年4月14日下午9:09

public class KReverseListNode {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入链表长度N和K值（链表的值默认是从1到N）");
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] nums = new int[N];
        for (int i = 1; i <= N; i ++) {
            nums[i - 1] = i;
        }
        ListNode head = ListNode.constructByNums(nums);
        ListNode resHead = reverseKGroup2(head, K);
        ListNode.printListNode(resHead);
    }
    static ListNode reverseKGroup2(ListNode head, int k) {
        ListNode head1 = reverseListNode(head);
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head1;
        ListNode pre = dummyHead;
        ListNode startHead = pre.next;
        ListNode endTail = pre;
        //给while()循环取一个标签end
        end:
        while (true) {
            startHead = pre.next;
            endTail = pre;
            for (int i = 0; i < k; i ++) {
                endTail = endTail.next;
                if (endTail == null) {
                    //一直跳到标签为end的循环
                    break end;
                }
            }
            ListNode nextHead = endTail.next;
            pre.next = null;
            endTail.next = null;
            ListNode[] nodes = reverseListNodeByStartAndEnd(startHead, endTail);
            pre.next = nodes[0];
            nodes[1].next = nextHead;
            pre = nodes[1];
        }
        return reverseListNode(dummyHead.next);
    }
    static ListNode[] reverseListNodeByStartAndEnd(ListNode start, ListNode end) {
        ListNode pre = null;
        ListNode tail = start;
        while (start != null) {
            ListNode temp = start.next;
            start.next = pre;
            pre = start;
            start = temp;
        }
        return new ListNode[]{pre, tail};
    }
    static ListNode reverseListNode(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
    static class ListNode {
        int val;
        ListNode next;
        public ListNode() {}
        public ListNode(int val) {
            this.val = val;
        }
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
        static ListNode constructByNums(int[] nums) {
            if (nums == null) {
                throw new NullPointerException();
            }
            if (nums.length <= 0) {
                return null;
            }
            List<ListNode> nodeList = new ArrayList<>(nums.length);
            for (int i = 0; i < nums.length; i ++) {
                ListNode node = new ListNode(nums[i]);
                nodeList.add(node);
                if (i - 1 >= 0) {
                    nodeList.get(i - 1).next = node;
                }
            }
            return nodeList.get(0);
        }
        static void printListNode(ListNode head) {
            StringBuilder res = new StringBuilder("[ ");
            while (head != null) {
                res.append(head.val);
                if (head.next != null) {
                    res.append(" -> ");
                } else {
                    res.append(" ");
                }
                head = head.next;
            }
            res.append("]");
            System.out.println(res.toString());
        }
    }
}

0 赞同 0 条回复

binto 普通 2023年4月14日下午5:06

const array = [1, 2, 6, 3, 4, 5, 6];

class LinkedNode {
    constructor(value, next) {
        this.value = value;
        this.next = next;
    }
}

function addNode(value) {
    const newNode = new LinkedNode(value, null);
    if (this.head == null)
        this.head = newNode;
    else {
        let curr = this.head;
        while (curr.next) {
            curr = curr.next;
        }
        curr.next = newNode;
    }
}

function CreateLinkList(arr) {
    if (arr.length < 1) return 0;
    this.head = null;

    for (let i = 0; i < arr.length; i++) {
        addNode(arr[i]);
    }
    return this.head;
}

// 链表反转
function reverseLinkedList(head) {
    if (head == null || head.next == null) {
        return head;
    }
    let newNode = reverseLinkedList(head.next);
    head.next.next = head;
    head.next = null;
    return newNode;
}

function reverseKGroup2(head, k) {
    let temp = head;
    // 链表分组
    for (let i = 1; temp != null && i < k; i++) {
        temp = temp.next;
    }
    if(temp == null) return head;
    let t = temp.next; 
    temp.next = null;
    // 组内反转
    let newHead = reverseLinkedList(head);

    let newGroup = reverseKGroup2(t, k);
    head.next = newGroup;
    return newHead;
}

const head = CreateLinkList(array);

// 整体反转->分组反转->再反转
const result = reverseLinkedList(reverseKGroup2(reverseLinkedList(head), 4));

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【作业7】字节真题：变形的链表反转

共以下 14 个回答

打卡

打卡

# 回答此问题 取消回复

# 回答此问题取消回复