10.206.反转一个单链表
/**
* @author mys
* @version 2019.8.14
* 反转一个单链表
*/
package com.mys;
import org.junit.Test;
public class ReverseList206 {
public ListNode reverseList(ListNode head) {
ListNode prev = null;//前结点
ListNode curr = head;//当前结点
while (curr != null) {
ListNode temp = curr.next;//临时节点,存放当前结点的下一节点
curr.next = prev;//当前节点 指向前节点
prev = curr;//前结点向后移
curr = temp;//当前节向后移
}
return prev;
}
@Test
public void fun() {
//初始化数据
ListNode a = new ListNode();
ListNode b = new ListNode();
ListNode c = new ListNode();
ListNode d = new ListNode();
ListNode e = new ListNode();
a.setVal(10);
b.setVal(20);
c.setVal(30);
d.setVal(40);
e.setVal(50);
a.setNext(b);
b.setNext(c);
c.setNext(d);
d.setNext(e);
e.setNext(null);
ListNode head = a;
System.out.println("before reverse:");
while (head != null) {
System.out.println(head.val);
head = head.next;
}
System.out.println("after reverse:");
ListNode reverse = reverseList(a);
while (reverse != null) {
System.out.println(reverse.val);
reverse = reverse.next;
}
}
}
class ListNode {
int val;//存储元素的数据域
ListNode next;//存储下一个节点的指针域
public void setVal(int val) {
this.val = val;
}
public void setNext(ListNode next) {
this.next = next;
}
public ListNode() {
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
11.169.给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在众数
public class MajorityElement169 {
//摩尔投票法
//假设第一个数过半数,后面如果相同加一,不同减一
//当count减为0时,重新更换数
public int majorityElement(int[] nums) {
int res = 0;
int count = 0;
for (int i = 0; i < nums.length; i ++) {
if (count == 0) {
res = nums[i];
count ++;
}else {
if (res == nums[i]) {
count++;
} else {
count--;
}
}
}
return res;
}