[数据结构与算法]一天一道小算法--单链表翻转/K个一组翻转

1.问题描述:

给定一个链表,输入这个链表翻转的结果.

比如 给定链表 1->2->3->4->5? 翻转之后输出5->4->3->2->1

方法1:头节点插入法:

思考: 如果每次把头节点取出来,然后指向上一次轮询取出的节点 是不是就可以了(第一次指向null);

按照如图的逻辑,最终输出newHead即可.

代码实现:

准备一个ListNode:

class  ListNode{
    private int val;
    private ListNode next;
//省略构造 get/set
}

翻转方法:

  public static ListNode reverse(ListNode headNode){
        if (headNode==null||headNode.next==null) {
            return headNode;
        }
        //记录当前剩余需要翻转的部分
        ListNode curr=headNode;
        //最终输出的
        ListNode newHead=null;
        while (curr!=null){
            //取出下一次循环需要翻转的部分
            ListNode nextCurr = curr.next;
            //当前节点执行newHead
            curr.next=newHead;
            //当前节点执行newHead newHead指向翻转后的链表段
            newHead=curr;
            curr=nextCurr;
        }
        return newHead;
    }
}

方法2: 尾节点 递归

思考:找出最后一个节点把要输出的newHead指向该节点 然后给该节点添加next

  public static ListNode reverse2(ListNode headNode){
        if (headNode==null||headNode.next==null) {
            return headNode;
        }
        //找出当前headNode的最后一个节点
        ListNode newHead = reverse2(headNode.next);
        //把当前headNode最后一个节点的next指向head本身   让后把heade的next置空
        headNode.next.next=headNode;
        headNode.next=null;
        return newHead;
}

升级: k(k>0)个每组进行翻转 不足k个输出原顺序

给定一个链表, 1->2->3->4->5->6->7-8-9-10? 给定k=4?则输出? 4->3->2->1,8->7->6->5,9->10

思考:如果可以找到截取点,进行截取 一部分进行判断是不是需要翻转 ,另一部分是待操作片段,最终输出不就可以了.

代码实现:

?

 public static void reverseKnode(ListNode headNode,int k){
        if (headNode==null||headNode.next==null) {
            return ;
        }
        while (headNode!=null){
            //需要翻转的部分开始的部分  start执行 headNode的头
            ListNode start=headNode;
            //等待被操作的部分
            ListNode end=null;
            for (int i = 1; i <= k; i++) {
                //切割点
                if (i%k==0&&headNode!=null){
                    end=headNode.next;
                    headNode.next=null;
                    //模拟输出
                    System.out.println(reverse2(start));
                }else if (headNode==null){ //不够k则不进行翻转
                    System.out.println(start);
                    break;
                }
                headNode=headNode.next;

            }
            headNode=end;
        }
    }

leetcode地址

高频考点? 高频考点 高频考点? dayday upup!!