实习+秋招刷题012-013（牛客刷题）

012反转链表
题目描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
如当输入链表{
   1,2,3}时，
经反转后，原链表变为{
   3,2,1}，所以对应的输出为{
   3,2,1}。
以上转换过程如下图所示：

关键解题思路

• 双指针，定义两个指针pre和cur,pre在前，cur在后；
• pre和cur之间进行局部反转；
• 局部反转结束后，pre，cur同时向右移动一个位置
• 循环上述过程，直到pre指向链表尾部

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类 * @return ListNode类 */
    public ListNode ReverseList (ListNode head) {
   
        ListNode cur= head;
        ListNode pre = null;
        while(cur!=null){
   
        //局部反转
            ListNode cur_next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = cur_next;
        }
        return pre;
    }
}

013 链表内指定区间反转
题目描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转.

关键解题思路
两个for循环实现

• 第一个for循环找到m所指向的节点；
• 第二个for循环是从m所指向节点出发，到n指向节点结束，循环体中定义两个节点pre和cur（pre在前，cur在后），利用头插法反转区间中链表，pre.next最终指向区间链表完成反转后的头节点。

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 m int整型 * @param n int整型 * @return ListNode类 */
    public ListNode reverseBetween (ListNode head, int m, int n) {
   
        // write code here
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode cur = head;
        ListNode pre= res;
        for(int i=1; i<m; i++){
   
            pre = cur;
            cur = cur.next;
        }
        //头插法
        for(int i=m ; i<n; i++){
   
            ListNode temp  = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return res.next;
    }
}