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

• ref
  • 25. K 个一组翻转链表
• contact
  • 滴滴算法题：K步长反转链表
• tag
  • 链表 递归 遍历

方法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 协议》，转载必须注明作者和本文链接