实习+秋招刷题014-015（牛客刷题）

014链表中的节点每k个一组翻转
题目描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

关键解题思路
递归
每k个节点为一组，每组进行一次翻转
终止条件：当最后一组节点不足k个，就直接返回
返回值：返回每组翻转后链表的头节点
本级任务：1、循环找到每组翻转前链表的尾部；2、从这组的开头依次两两翻转到结尾；3、翻转后的尾节点就是下一组的头部。
Solution

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */

public class Solution {
   
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */
    public ListNode reverseKGroup (ListNode head, int k) {
   
        // write code here
        //尝试头插法
        // ListNode res = new ListNode(-1);
        // res.next = head;
        
        ListNode tail = head;
        for(int i=0; i<k; i++){
   
            if(tail == null)
                return head;
            tail = tail.next;
        }
        ListNode cur = head;
        ListNode pre = null;
        //翻转,两两交换方向
        while(cur != tail){
   
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur= temp;
        }
        head.next = reverseKGroup(cur, k);
        return pre;
    }
}

015合并两个排序的链表
题目描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

关键解题思路
双指针，分别指向当前访问两个链表中的节点
1、定义新链表头节点head
2、循环
结束条件：两个链表中的两个当前访问节点中任意一个节点为null
循环体：比较当前访问两个链表中的节点值大小，然后将head指向小的那个节点，并且相应的链表节点要后移一位。
3、其他情况，如果两个链表的当前节点任意一个当前节点不为null，head直接指向该节点。
Solution

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */

public class Solution {
   
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类 */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
   
        // write code here
        if(pHead1==null){
   
            return pHead2;
        }
        if(pHead2==null){
   
            return pHead1;
        }
        ListNode head = new ListNode(0);
        ListNode anshead = head;
        while(pHead1!=null && pHead2!=null){
   
            if(pHead1.val>pHead2.val){
   
                head.next = pHead2;
                pHead2 = pHead2.next;
                }
            else{
   
                head.next = pHead1;
                pHead1 = pHead1.next;
            }
            head = head.next;
        }
        if(pHead1!=null){
   
            head.next = pHead1;
        }
        if(pHead2!=null){
   
            head.next = pHead2;
        }
        return anshead.next;
    }
}