JAVA详细版 重排链表

重排链表

http://www.nowcoder.com/questionTerminal/3d281dc0b3704347846a110bf561ef6b

解法一 线性表

我们都知道链表的缺点是查询效率低,每一次都需要从头开始遍历。所以如果按照题目的要求组成新链表,要去得到最后一个节点,就得从头将链表遍历一次,这样反复操作,直到将原来的链表改变到题目要求的链表。这样很明显是非常耗时间的。、

由于有了上面的分析,直到了这一缺点,我们就可以想到与链表齐名的数组了。

我们知道数组想访问某一个元素的时候,可以通过下标直接去访问它,这不就是我们想要的吗?

所以下面我们先来一个简单粗暴的方法,因为我们知道ArrayList的底层就是用数组实现的,所以我们将链表储存在一个ArrayList中,然后利用双指针,一个指向最前面,一个指向最后面,依次访问并向题目要求的链表形式进行转换!

class Solution {
    public void reorderList(ListNode head) {
        if(head == null)
            return;
        List<ListNode> list = new ArrayList<>();   //  ArrayList为线性表
        // 将 链表的每一个节点依次 存进ArrayList中
        while(head != null){
            list.add(head);
            head = head.next;
        }
        // 两个指正依次从前 后进行遍历取元素
        int i = 0, j = list.size()-1;
        while(i < j){
            //  eg:  1->2->3->4
            // 前面的节点的下一个节点指向最后的节点
            list.get(i).next = list.get(j);  //  即 1->4
            i++;  // 此时 i++ 则此时 list.get(i) 为原来前面节点的下一个节点   即节点2
            if(i == j) // 若 链表长度为偶数的情况下 则会提前相遇,此时已达到题目要求,直接终止循环
                break;
            list.get(j).next = list.get(i);   // 4->2
            // 此时刚刚的例子则变为  1->4->2->3
            j--;
        }
        list.get(i).next = null;  // 最后一个节点的下一个节点为null
    }
}

解法二:三步走

eg: 1->2->3->4->5->6

第一步:将链表分为两个链表

​ 1->2->3 4->5->6

第二步:将第二个链表逆序

​ 1->2->3 6->5->4

第三步:依次连接两个链表 连接形式如下

​ 1->6->2->5->3->4

第一步 找中间

链表的中间节点,如果这道题你已经AC了,那么第一步你就成功了!

思路:可以利用 快慢指针,快指针一次走两步,慢指针依次走一步,当快指针走到终点的时候,此时如果链表的长度为偶数时,此时中间节点有两个,慢指针则走到了左端点。反之,慢指针则走到中间节点。(这两种情况在我们这道题目的总代吗,我们可以直接合并为一种,则第二个链表的长度比第一个链表的长度小1)

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null)
            return head;
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast.next == null)  // 长度为奇数
            return slow;
        else
            return slow.next;  // 长度为偶数
    }
}

第二步 反转链表

同样先跳到反转链表

思路:

迭代法,声明一个尾结点 用于 储存头结点,此时头结点指向下一个结点,并且尾结点的下一个结点指向null

由于我们想要反转链表,所以此时的头结点的下一个节点则需要指向上面的尾结点,这样就实现了第一二个结点反转了,但是此时头结点原来的下一个结点会被覆盖,所以也需要储存起来。下面直接贴出代码

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null)
            return head;
        ListNode tail = head;
        head = head.next;
        tail.next = null;

        while(head != null){
            ListNode temp = head.next;  // temp储存了此时头结点的下一个结点
            head.next = tail;     // 头结点的下一个结点指向 tail
            tail = head;     // 此时的头结点则变为尾结点
            head = temp;    // 刚刚储存起来的结点则为头结点
        }
        return tail;
    }
}

第三步 合并两个链表

思路:直接两个指正往后遍历即可

        newHead = reverseList(newHead);
        while(newHead != null){
            ListNode temp = newHead.next;
            newHead.next = head.next;
            head.next = newHead;
            head = newHead.next;
            newHead = temp;
        }

最后贴出总的代码

public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null)
            return;

        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        ListNode newHead = reverse(mid);


        while(newHead != null){
            ListNode temp = newHead.next;
            newHead.next = head.next;
            head.next = newHead;
            head = newHead.next;
            newHead = temp;
        }
    }

    //反转链表
    public ListNode reverse(ListNode head){
        if(head == null)
            return head;
        ListNode tail = head;
        head = head.next;
        tail.next = null;
        while(head != null){
            ListNode tmp = head.next;
            head.next = tail;
            tail = head;
            head = tmp;
        }
        return tail;
    }

}

总结:

解法一的方法利用线性表进行储存,很好的利用了线性表易访问的特点来弥补链表本身访问需要从头开始遍历的缺点,这样就将问题远远简单化了,省去了每次去遍历的步骤;

解法二的方法则将问题分成三步,从一个大问题分解为三个小问题,这在解题中其实也不失为一种好办法。因为当你一步一步写出你的思路的时候,你会发现问题就能迎刃而解,即使解法很笨拙或者繁琐,但是这也加深了对题目的理解。

全部评论
第一种解法不要判断i==j运行起来也一样啊?
1 回复 分享
发布于 2021-06-09 15:44

相关推荐

哈哈哈哈哈哈哈哈哈哈这个世界太美好了
凉风落木楚山秋:毕业出路老师不管,你盖个章他好交差就完事了,等你盖完毕业了就不关他事情了
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
评论
51
18
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务