【牛客面试必刷101】- 反转链表+数组中出现次数超过一半的数字+链表内指定区间反转

seven_ • 2023年2月28日上午10:49 • 后端笔记 • 阅读 240

1.反转链表

这个方法就是 头插法，从原链表头开始取元素，对新链表进行头插法。
具体代码如下:

public ListNode ReverseList(ListNode head) {
    //新链表
    ListNode newHead = null;
    while (head != null) {
        //先保存访问的节点的下一个节点，保存起来
        //留着下一步访问的
        ListNode temp = head.next;
        //每次访问的原链表节点都会成为新链表的头结点，
        //其实就是把新链表挂到访问的原链表节点的
        //后面就行了
        head.next = newHead;
        //更新新链表
        newHead = head;
        //重新赋值，继续访问
        head = temp;
    }
    //返回新链表
    return newHead;
}

在牛客上看到的题解，特别清晰

2.链表内指定区间反转

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    //
    //说明：方便理解，以下注释中将用left，right分别代替m,n节点

    public ListNode reverseBetween (ListNode head, int m, int n) {
        //设置虚拟头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < m - 1; i++) {
            pre = pre.next;
        }

        ListNode cur = pre.next;
        ListNode Cur_next ;
        for (int i = 0; i < n - m; i++) {
            Cur_next = cur.next;
            cur.next = Cur_next.next;
            Cur_next .next = pre.next;
            pre.next = Cur_next ;
        }
        return dummyNode.next;
    }
}

3.数组中出现次数超过一半的数字

import java.util.Arrays;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int mid = array.length / 2;
        int count = 0;
        Arrays.sort(array);
        for (int i = 0; i < array.length; i++) {
            if (array[i] == array[mid]) {
                count++;
            }
        }
        if (count > mid) {
            return array[mid];
        }

        return  0 ;
    }
}