【Daily LeetCoding Challenge14】 K 个一组翻转链表

【Daily LeetCoding Challengeday14】 K 个一组翻转链表

大家好，我是小王

为了不别人KO,话不多说，直接干货

前言

据说 这是字节 面试题，单链表 你会翻转 需要3个指针，

1. 主要观察区别，phead 每组翻转完毕后 需要重置
2. phead 从哪里来呢 链表 无法倒序 ，需要ppre 记录 pcur前面一个位置。

思路

• K 个一组翻转链表

  //init： myeahd(phead||ppre)->1(pcur)--2--3--4--5

  //initmyeahd-->2 -1(phead||ppre) --3(pcur) -4 -5

  • 最关键地方：k组翻转完毕后，忘记重置 3. for 循环 死循环 写多少次 每次都都有小错误

最关键地方：k组翻转完毕后，需要重置

时间复杂度

• o(n)

代码

• 剑指 Offer 24. 反转链表 c++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
      
       ListNode* phead = NULL; //无固定头节点的单链表。转后链表的头节点
       ListNode* pnext = NULL; // 防止迷路
       ListNode* pcur =  head;
       
        //链表适中在head插入
       while (pcur) 
       {
           pnext = pcur->next; // 1--2

           pcur->next = phead; //1->NULL
           phead = pcur; //phead->1--null;

           pcur = pnext;// move like ++

       }

       return  phead;

    }
};

• 单链表翻转go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    
    //三路指针 
    var phead *ListNode 
    var pnext *ListNode    
    var pcur  *ListNode   

    phead = nil
    pnext = nil
    pcur = head 
    
    // 遍历 翻转
    for pcur != nil {

        pnext      = pcur.Next
        pcur.Next  = phead //这里是指针 非固定节点，不需要phead.NEXT
        phead     =pcur //这里是指针 非固定节点，不需要phead.NEXT 一直在变化
        pcur  = pnext //迭代
    }

    return phead
    

}

25. K 个一组翻转链表 c++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
      //单链表翻转 翻转全部元素，这里翻转k个 区别是什么? 
      //单链表翻转是 一个old 链表 构造 一个新的链表 其实 2个链表 
      // k 必须 部分翻转。原地翻转 

      // K <= n  
      //If the number of nodes is not a multiple of k then left-out nodes, 
      //in the end, should   remain as it is.
      if (nullptr == head  || nullptr == head->next ||  k <= 0 ) return head;
       

      //01 k个一组，最后不翻转

      ListNode* ptemp = head;
      int count = 0;
      while(ptemp)
      {
          ptemp = ptemp->next;
          count++;
      }
      //02 定义遍历
       ListNode myhead(-1,head);
        
       //三路指针第一次初始化 
       ListNode* phead =  &myhead;
       ListNode* pcur  = head;
       ListNode* ppre = &myhead;

       //03 顺序遍历 k组翻转一次 然后初始化三路指针
       for (int group = count/k;group > 0 ;group--){
           //每次翻转k元素
           for(int i = 0;i <k ;i++)
           {   
                if (phead->next == pcur){
                     ppre  = pcur;
                     pcur = pcur->next;
                }else {
                ppre->next =pcur->next; 
                pcur->next = phead->next; 
                phead->next =pcur;
                pcur =ppre->next;//move
                }
           }

           //翻转第二组时候，需要重置phead位置 
            if( pcur) {
               phead =  ppre; // 单链表翻转 phead 第一位置，这里不是 区别！！！每组的第一个位置
            }
       }

       return myhead.next;
    }
};

如何学习

一、这个技术出现的背景、初衷和要达到什么样的目标或是要解决什么样的问题

二、这个技术的优势和劣势分别是什么

三、这个技术适用的场景。任何技术都有其适用的场景，离开了这个场景

四、技术的组成部分和关键点。

五、技术的底层原理和关键实现

六、已有的实现和它之间的对比