精华内容
下载资源
问答
  • 给出一个链表和一个数K,比如链表1->2->3->4->5->6->NULL,K=2,翻转后 2->1->4->3->6->5->NULL,若K=3,翻转后3->2->1->6->5->4->NULL,若K=4,翻转后4->3->2->1->5->6->NULL,用程序实现ListNode* RotateList...

    链表翻转。给出一个链表和一个数K,比如链表1->2->3->4->5->6->NULL,K=2,翻转后 2->1->4->3->6->5->NULL,若K=3,翻转后3->2->1->6->5->4->NULL,若K=4,翻转后4->3->2->1->5->6->NULL,用程序实现ListNode* RotateList(ListNode* list, size_t k)

    递归实现

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *reverseKGroup(ListNode *head, int k) {
            // 为空或一个结点或 K 不符合 规范直接返回原head
            if( NULL == head || NULL == head->next || k < 2)
                return head;
    
            // 以k为步数,找到逆置前下一组的头指针
            ListNode* next_group_head = head;
            for(int i = 0; i < k; ++i){
                if(next_group_head)   
                    next_group_head = next_group_head->next;
                else // 剩余结点数小于K 不够分一组时,下一组的头指针就是head
                    return head;
            }
    
            // 递归去处理剩余组,直到不够 K 个结点,即求出下一组逆置后的头指针
            ListNode* new_next_group_head = reverseKGroup(next_group_head, k);
            ListNode* prev = NULL ,* cur = head;
            // 开始逆置处理当前组,从 head --- next_group_head下一组逆置前的第一个结点
            while(cur != next_group_head){
                ListNode* next = cur->next; // 保存下一个结点
                if(prev == NULL)      // 为空则将当前组的一个结点指向下一组逆置后的第一个结点
                    cur->next = new_next_group_head;
                else                  // 不为空则表示逆置当前组的结点,指向prev即可
                    cur->next = prev;
                prev = cur;   // 向后推进,直到走完当前组
                cur = next;           
            }
            // 返回逆置后的头指针
            return prev;
        }
    };

    迭代解法

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
         ListNode *reverseKGroup(ListNode *head, int k)
        {
            // 特殊情况处理
            if (NULL == head || NULL == head->next || k < 2)
                return head;
    
            ListNode* prev = NULL, *pcur = head, *newhead = NULL;
    
            // 遍历链表,处理每一组
            while (pcur){
    
                // 找到下一组的头
                ListNode* next_group_head = pcur;
                int i = 0;
                for (; next_group_head && i < k; i++){
                    next_group_head = next_group_head->next;
                }
                // 处理不足K 个元素的组
                if (i < k ){
                    // 防止K 大于链表结点
                    if (newhead == NULL)
                        newhead = head;
                    break;
                }
                // 将当前分组[pcur, next_group_head) 逆置,并返回逆置后的头指针
                ListNode* tmp = reverse(pcur, next_group_head);
    
                if (prev == NULL) // 第一个分组需要更新新的头指针
                    newhead = tmp;
                else  // 后续只需要将上一个分组的最后一个结点next 指向当前分组逆序后的的头指针
                    prev->next = tmp;
                // 当前分组的最后一个结点next 指向下一个分组开始
                pcur->next = next_group_head;
                // prev 保存当前分组的最后一个结点
                prev = pcur;
                // pcur 向后推进到下一个分组的开始
                pcur = next_group_head;
            }
            return newhead;
        }
        //    [start, end)
        ListNode* reverse(ListNode* start, ListNode* end)
        {
            ListNode* prev = NULL;
            ListNode* pcur = start;
            while (pcur != end){
                ListNode* next = pcur->next;
                pcur->next = prev;
                prev = pcur;
                pcur = next;
            }
            return prev;
        }
    };
    展开全文
  • 给出一个链表和一个数k,比如链表1→2→3→4→5→6,k = 2,翻转后2→1→4→3→6→5,若k = 3, 翻转后3→2→1→6→5→4,若k = 4,翻转后4→3→2→1→5→6。 这是一道美团网的现在上面是题,下面有个人的做法,对...

    问题描述:
    给出一个链表和一个数k,比如链表1→2→3→4→5→6,k = 2,翻转后2→1→4→3→6→5,若k = 3, 翻转后3→2→1→6→5→4,若k = 4,翻转后4→3→2→1→5→6。
    这是一道美团网的现在上面是题,下面有个人的做法,对大家进行讲解,程序猿最直接的自然是代码,话不多说先上代码:

    #include<iostream>
    #include<stdlib.h>
    using namespace std;
    
    struct ListNode
    {
        int _data;
        ListNode* _next;
    
        ListNode(int x = 0)
            :_data(x)
            , _next(NULL)
        {}
    };
    
    typedef ListNode Node;
    
    Node* createList(int* arr, int length) {
        Node* pHead = NULL;
        Node* pTemp, *pNode;
        pTemp = NULL;
        for (int i = 0; i < length; i++) {
            pNode = (Node*)malloc(sizeof(Node));
            pNode->_data = arr[i];
            pNode->_next = NULL;
            if (NULL == pHead)
                pHead = pNode;
            else
                pTemp->_next = pNode;
            pTemp = pNode;
        }
        return pHead;
    }
    
    void destroyList(Node* pHead) {
        Node* pNode;
        while (pHead) {
            pNode = pHead;
            pHead = pHead->_next;
            free(pNode);
        }
    }
    
    void PrintfList(Node* head)
    {
        Node* phead = head;
        while (phead)
        {
            cout << phead->_data << " ";
            phead = phead->_next;
        }
        cout << endl;
    }
    
    Node* reverseList(Node* pHead) {
        if (NULL == pHead || NULL == pHead->_next)
            return pHead;
        Node* pNode;
        Node* pNewHead = NULL;
        while (pHead) {
            pNode = pHead;
            pHead = pHead->_next;
            pNode->_next = pNewHead;
            pNewHead = pNode;
        }
        return pNewHead;
    }
    
    Node* getLastNode(Node* pHead) {
        while (NULL != pHead->_next)
            pHead = pHead->_next;
        return pHead;
    }
    
    Node* swapListByK(Node* pHead, int k) {
        if (k <= 1)
            return pHead;
        int pos;
        Node* pNode = pHead;
        Node* pNewHead;
        Node* pNextNode;
        Node* pLastNode = NULL;;
        pHead = NULL;
        while (pNode) {
            pos = 0;
            pNewHead = pNode;
            while (pNode && pos < k - 1) {
                pNode = pNode->_next;
                pos++;
            }
            if (pNode) {
                pNextNode = pNode->_next;
                pNode->_next = NULL;
                if (NULL != pLastNode) {
                    pLastNode->_next = NULL;
                }
                pNewHead = reverseList(pNewHead);
                if (NULL == pHead) {
                    pHead = pNewHead;
                }
                else {
                    pLastNode->_next = pNewHead;
                }
                pNode = getLastNode(pNewHead);
                pNode->_next = pNextNode;
                pLastNode = pNode;
                pNode = pNextNode;
            }
            else {
                break;
            }
        }
        return pHead;
    }
    
    int main()
    {
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int length = sizeof(arr) / sizeof(arr[0]);
        Node* pHead = createList(arr, length);
        pHead = swapListByK(pHead, 2);
        PrintfList(pHead);
        destroyList(pHead);
        system("pause");
        return 0;
    }

    解题思路在于每一个变换节点指向的保存,翻转次数的确定,通过循环,两者之间相互交替工作,完成任务。循环变量的控制,就是翻转次数k,每完成一次k=k-1,当k<0时,退出循环。
    首先要有新的链表的头指针,以及没有旋转部分的头指针,旋转部分的最后一个节点的指针,这是最重要的三部分,还有就是旋转过程中的中间变量。将旋转动作单独封装为一个动作,进行调用。

    展开全文
  • 给出一个链表和一个数k,比如链表1→2→3→4→5→6,k=2,翻转后2→1→4→3→6→5,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→5→6,提示:这个题是链表逆置的升级变型。 代码: pNode RotateList...

    链表翻转。

    给出一个链表和一个数k,比如链表1→2→3→4→5→6,k=2,翻转后2→1→4→3→6→5,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→5→6,提示:这个题是链表逆置的升级变型。

    代码:

    pNode RotateList(pNode* pHead, DataType k)
    {
    	pNode pPre = Find(*pHead, k);
    	pPre = pPre->next;
    	pNode pCur = *pHead;
    
    	pNode pNewNode = NULL;
    	pNode pCur2 = NULL;
    	while (pCur != pPre)
    	{
    		pNewNode = pCur;
    		pCur = pCur->next;
    		pNewNode->next = pCur2;
    		pCur2 = pNewNode;
    	}
    	(*pHead)->next = pPre;
    	return pNewNode;
    }


    展开全文
  • Java实现 LeetCode 25 K个一组翻转链表

    万次阅读 多人点赞 2020-02-12 20:29:22
    一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表k一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。 示例 : 给定这个链表:1->...

    25. K 个一组翻转链表

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

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

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

    示例 :

    给定这个链表:1->2->3->4->5

    当 k = 2 时,应当返回: 2->1->4->3->5

    当 k = 3 时,应当返回: 3->2->1->4->5

    说明 :

    你的算法只能使用常数的额外空间。
    你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/reverse-nodes-in-k-group
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    PS:
    这链表你品 你细品~~~

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
         public ListNode reverseKGroup(ListNode head, int k) {
            ListNode prev = null;
            ListNode cur = head;
            ListNode next = null;
            ListNode check = head;
            int canProceed = 0;
            int count = 0;
            // 检查链表长度是否满足翻转
            while (canProceed < k && check != null) {
                check = check.next;
                canProceed++;
            }
            // 满足条件,进行翻转
            if (canProceed == k) {
                while (count < k && cur != null) {
                    next = cur.next;
                    cur.next = prev;
                    prev = cur;
                    cur = next;
                    count++;
                }
                if (next != null) {
                    // head 为链表翻转后的尾节点
                    head.next = reverseKGroup(next, k);
                }
                // prev 为链表翻转后的头结点
                return prev;
            } else {
                // 不满住翻转条件,直接返回 head 即可
                return head;
            }
        }
    }
    
    展开全文
  • 给出一个链表和一个数k,比如链表1→2→3→4→5→6,k=2,翻转后2→1→4→3→6→5,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→5→6,用程序实现Node* RotateList(Node* list, size_t k). 提示:这个...
  • 给出一个单向链表的头指针,输出该链表中倒数第K个节点的指针,链表的倒数第0个节点为链表的尾节点(尾节点的next成员为NULL)  NODE* findnode(NODE *head,unsigned int k);  思路:首先求单向链表的长度...
  • 链表-找单链表中倒数第k个数

    千次阅读 2019-03-10 08:43:25
  • 给出一个链表和一个数k,比如链表1→2→3→4→5→6,k=2,则翻转后2→1→4→3→6→5,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→5→6 基本思想: 链表中长度为k的一段从链表中摘除,翻转之后在...
  • 用其中一个指针遍历链表,当该指针遍历到第k个节点时,另外一个指针开始从头节点开始遍历链表;两个指针之间的距离为k;遍历完链表时第二个指针所指向的节点就是倒数第K个: #include #include #include using ...
  • 给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。 示例 : 给定这个链表:1-&...
  • 解题思路 /** * 两指针p1,p2,开始都指向头结点 ... * 当p2指向null的时候,p1就是倒数第k个节点 */ 代码 /* class ListNode { int val; ListNode next = null; ListNode(int val) { this.v...
  • LeetCode 链表翻转(按K个一组) 详解

    千次阅读 2018-09-02 17:09:27
    给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。 示例 : 给定这个链表:1-&...
  • 题目描述给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。示例 :给定这个链表:1-&...
  • 链表翻转,每K个数翻转次。

    千次阅读 2017-07-23 22:10:27
    链表翻转,每K个数翻转次,比如链表1→2→3→4→5→6,k=2,翻转后2→1→4→3→6→5,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→5→6。   解题思路:   寻找每段的开始与结束,对每段...
  • 给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。 示例 : 给定这个链表:1-&...
  • 输入一个单向链表,输出该链表中倒数第K
  • 输入一个链表,输出该链表中倒数第k个结点。 示例1 输入 1,{1,2,3,4,5} 返回值 {5} 思路1:暴力查找 直接遍历链表,算出链表长度n,然后倒数第k个,就是输出链表正数第n-k个 注意:以下几种情况直接返回NULL ...
  • leetcode25. K 个一组翻转链表

    千次阅读 热门讨论 2020-02-15 15:59:13
    一个链表,每k个节点一组进行翻转,请你返回翻转后的链表k一个正整数,它的值小于或等于链表的长度。 如果节点总数不是k的整数倍,那么请将最后剩余的节点保持原有顺序。 示例 : 给定这个链表:1->2...
  • 给出链表中的节点每k个一组翻转,返回翻转后的链表 如果链表中的节点不是k的倍数,将最后剩下的节点保持原样 你不能更改节点中的值,只能更改节点本身。 只允许使用常数级的空间 例如: 给定的链表是1-&...
  • 输入一个链表,输出该链表中倒数第k个结点。 解题思路: 1、当输入的链表为空的时候直接返回空 2、当输入的k值大于链表的节点的时候直接返回null; 3、先遍历链表得出链表的节点,(注意;因为后面需要重新遍历...
  • 合并K个有序链表

    万次阅读 2018-03-20 21:24:52
    思路:将K个有序链表的首节点放入堆中,并且维护最小堆的性质,然后依次拿走堆顶的元素,每拿走堆顶的元素,是新放一个元素到堆顶 还是将堆的最尾端的元素置换到堆顶,取决于,拿走的元素是否有下一个节点,并且每...
  • Leetcode K个一组翻转链表

    千次阅读 2021-01-21 22:56:02
    一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表k一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。 说明: 你的算法只能...
  • 剑指offer:输入一个链表,输出该链表中倒数第k个结点。 思路:由于单项链表不能回头,我思考了两种方法 方法一:先遍历链表,算出链表节点count,第二次直接遍历到第count-k个节点。但是要注意,可能链表结点数...
  • 合并k个有序链表

    千次阅读 2019-04-25 21:43:01
    、分治法 ...博主今天在刷LeetCode的时候遇到了这么题,合并K个有序链表,题号是23,我这里了链接,有兴趣的可以去看看,我今天就来用分治的策略来分析一下这题目。   接下来就来针对这题来...
  • '''输入一个链表,输出该链表中倒数第k个结点''' #常规解法,考虑了代码的鲁棒性,考虑了空指针,K为0,K大于链表的长度 class Solution: def FindKthToTail(self, head, k): # write code here if (head == None...
  • 025 K个一组翻转链表

    千次阅读 2018-04-17 15:47:37
    给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表k一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。 示例 : 给定这个链表:1-&...
  • 问题:请给出一个时间为O(nlgk),用来将k个已排序链表合并为一个排序链表的算法。此处的n为所有输入链表中元素的总数。 编程思路: 假设k链表都是非降序排列的。 (1)取k个元素建立最小堆,这k个元素分别是k个...
  • 链表K个节点翻转

    2017-07-25 13:29:11
    给出一个链表和一个数k,比如链表1→2→3→4→5→6,k=2,翻转后2→1→4→3→6→5,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→5→6,用程序实现Node* RotateList(Node* list, size_t k). 提示:这个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 208,851
精华内容 83,540
关键字:

给出一个链表和一个数k