首页 > 其他 > 详细

栈和队列----将单链表的每K个节点之间逆序

时间:2018-07-19 23:57:48      阅读:217      评论:0      收藏:0      [点我收藏+]

将单链表的每K个节点之间逆序

  

  给定一个单链表的头节点head,实现一个调整链表的函数,使得每K 个节点之间逆序,如果最后剩下不够K 个节点,则不调整最后几个。

  例如:

  链表:1—>2—>3—>4—>5—>6—>7—>8—>null,k=3。

  调整好后:3—>2—>1—>6—>5—>4—>7—>8—>null,其中7、8不调整,因为不够一组。

  

  【解析】

  1. 首先从左到右遍历链表,如果栈的大小不等于k ,则不断的入栈

  2. 当栈的大小等于k 时,不断的出栈,并重新连接这些节点

  3. 最后应该返回 newHead

package com.test;

import com.test.ListNode;

import java.util.Stack;

/**
 * Created by Demrystv.
 */
public class ReverseListNodeEveryK {

    /**
     * 使用栈的数据结构,时间复杂度是O(N),空间复杂度是O(N)
     */
    public ListNode reverseListNodeEveryK(ListNode head, int k){
        if (k < 2){
            return null;
        }
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode newHead = head;
        ListNode cur = head;
        ListNode pre = null;
        ListNode next = null;
        while (cur != null){
            next = cur.next;
            stack.push(cur);
            if (stack.size() == k){
                pre = resign1(stack, pre, next);
                // 举例说明可得证,例如k = 3
                // 如果是1 2 ,那么不需要反转,程序也执行不到这个if里面来,所以返回的是 头节点
                // 如果是1 2 3 4 ,当执行到3的时候,到了这个if里面,这时满足newHead==head,所以newHead就是3,符合反转后  3 2 1 4
                // 如果是1 2 3 4 5 6 7,执行到3,newHead是3,执行到6,不满足newHead==head,所以newHead就是newHead,就是3,符合 3 2 1 6 5 4 7
                // 真是巧妙呀!!!
                newHead = newHead == head ? cur : newHead;
            }
            cur = next;
        }
        return newHead;
    }

    private ListNode resign1(Stack<ListNode> stack, ListNode left, ListNode right){
        ListNode cur = stack.pop();
        if (left != null){
            left.next = cur;
        }
        ListNode next = null;
        while (!stack.isEmpty()){
            next = stack.pop();
            cur.next = next;
            cur = next;
        }
        // 实际传入的这个right参数,是下一个K 范围内的第一个节点,不属于这个k 范围内。
        // 确保与后面的相连
        cur.next = right;
        // 实际返回的这个cur 是这个K范围内的最后一个节点,即下一个k 的上一个节点,即pre 的意思
        return cur;
    }
}

 

栈和队列----将单链表的每K个节点之间逆序

原文:https://www.cnblogs.com/Demrystv/p/9339021.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!