《LeetCode 力扣》 - 25. K 个一组翻转链表 (遍历/递归)

《LeetCode 力扣》 - 25. K 个一组翻转链表 (遍历/递归)

方法1 遍历

  • 步骤
    • 1、链表 = 已翻转链表 + 待翻转子链表 + 未翻转子链表 + 无需反转子链表
      • 待翻转子链表:需要走 k 步
      • 无需反转子链表:走不到 k 步
    • 2、记录待翻转子链表
      • prev 待翻转子链表的头结点前驱
      • end 待翻转子链表的尾结点本身
      • start = prev->next 待翻转子链表的头结点
    • 3、记录未翻转子链表(为啥要记录,不然丢了咋办,嘻嘻嘻)
      • next = end->next
    • 4、待翻转子链表 (reverse 翻转单链表)
      • 拿到子链表的头结点是 start
      • 子链表的尾结点是 end
      • 切断尾结点的 next
      • 完成翻转 reverse(start)
    • 5、恢复链表的翻转,准备下一次的翻转
      • start->next = next (把第三步的 next 恢复到 start 上)
      • prev = start
      • end = start
  • 复杂度
    • 时间复杂度 O(n*k)
    • 空间复杂度 O(1)
//  * Definition for a singly-linked list.
class ListNode
{
    public $val = 0;
    public $next = NULL;
    function __construct($val = 0, $next = NULL)
    {
        $this->val = $val;
        $this->next = $next;
    }
}


class Solution {

    /**
     * k步长反转链表
     * 
     * @param ListNode $head
     * @param Integer $k
     * @return ListNode
     */
    function reverseKGroup($head, $k) {
        if($head == NULL || $head->next == NULL || $k <= 1) {
            return $head;
        }

        $dummy = new ListNode(0, NULL);
        $dummy->next = $head;

        $prev = $dummy;
        $end = $dummy;

        while($end->next != NULL) {
            // 【模拟-寻找待翻转子链表】
            for($i = 0; ($i < $k) && $end != NULL; $i++) {
                $end = $end->next;
            }
            if($end == NULL) {
                break;
            }
            // 【记录-待翻转子链表】
            $start = $prev->next;
            $next = $end->next;
            $end->next = NULL;

            // 【翻转-待翻转子链表】
            $prev->next = $this->reverse($start);

            // 【重置-变量准备下一次的待翻转子链表】
            $start->next = $next; // 承接后半部分
            $prev = $start;
            $end  = $start;
        }
        return $dummy->next;
    }

    /**
     * 单链表反转
     *
     * @param ListNode $head 链表头部
     * @return ListNode
     */
    public function reverse($head)
    {
        if($head == NULL || $head->next == NULL) {
            return $head;
        }
        $prev = NULL;
        $curr = $head;
        $next = NULL;

        while($curr != NULl) {
            $next = $curr->next;
            $curr->next = $prev;
            $prev = $curr;
            $curr = $next;
        }
        return $prev;
    }
}

方法2 递归

  • 步骤
    • 1、判断是否支持翻转 ,满足 k 步长
    • 2、单链表的翻转,翻转 k 步长
    • 3、得到待翻转子链表的头结点, curr ,继续递归子链表
    • 4、head 成为当前已翻转链表的末尾结点, head->next 将是下一个递归的开始点
  • 复杂度
    • 时间复杂度 O(n*k)
    • 空间复杂度 O(n)
class Solution {

    /**
     * k步长反转链表
     * 
     * @param ListNode $head
     * @param Integer $k
     * @return ListNode
     */
    function reverseKGroup($head, $k) {
        if($head == NULL || $head->next == NULL || $k <= 1) {
            return $head;
        }
        $isK = $head;
        for($i = 0; $i < $k; $i++) {
            if($isK == NULL) {
                return $head;
            }
            $isK = $isK->next;
        }

        $prev = NULL;
        $curr = $head;
        $next = NULL;
        for($i = 0; $i < $k; $i++) {
            $next = $curr->next;
            $curr->next = $prev;
            $prev = $curr;
            $curr = $next;
        }

        $head->next = $this->reverseKGroup($curr, $k);

        return $prev;
    }
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
明天我们吃什么 悲哀藏在现实中 Tacks
讨论数量: 3

邀请你在 1024 上分享你的这篇博文呢~

5个月前 评论
Tacks (楼主) 5个月前
May666 (作者) 2个月前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!