/**

/**

public ListNode reverseList(ListNode head) {

//申请节点，pre和 cur，pre指向null

ListNode pre = null;

ListNode cur = head;

ListNode tmp = null;

while (cur != null) {

//记录当前节点的下一个节点

tmp = cur.next;

//然后将当前节点指向pre

cur.next = pre;

//pre和cur节点都前进一位

pre = cur;

cur = tmp;

}

return pre;

}

/**

public ListNode reverseList2(ListNode head) {

//递归终止条件是当前为空，或者下一个节点为空

if (head == null || head.next == null) {

return head;

}

//这里的cur就是最后一个节点

ListNode cur = reverseList(head.next);

//这里请配合动画演示理解

//如果链表是 1->2->3->4->5，那么此时的cur就是5

//而head是4，head的下一个是5，下下一个是空

//所以head.next.next 就是5->4

head.next.next = head;

//防止链表循环，需要将head.next设置为空

head.next = null;

//每层递归函数都返回cur，也就是最后一个节点

return cur;

}

/**

public ListNode reverseList3(ListNode head) {

// 申请两个链表 一个空链表，一个完整的链表

ListNode pre = null;

ListNode curr = head;

while (curr != null) {

ListNode temp = curr.next;

curr.next = pre; // 当前链表指向 新链表

pre = curr; // 赋值给新链表

curr = temp;

}

return pre;

}

/**

public ListNode reverseList4(ListNode head) {

return putPreAfterNode(head, null);

}

private ListNode putPreAfterNode(ListNode node, ListNode pre) {

if (node == null) {

return pre;

}

ListNode next = node.next;

node.next = pre;

return putPreAfterNode(next, node);

}

/**

public ListNode swapPairs(ListNode head) {

if (head == null || head.next == null) {

return head;

}

ListNode next = head.next;

head.next = swapPairs(next.next);

next.next = head;

return next;

}

/**

public ListNode swapPairs2(ListNode head) {

ListNode pre = new ListNode(0);

pre.next = head;

ListNode temp = pre;

while (temp.next != null && temp.next.next != null) {

ListNode start = temp.next;

ListNode end = temp.next.next;

temp.next = end;

start.next = end.next;

end.next = start;

temp = start;

}

return pre.next;

}

/**

public boolean hasCycle(ListNode head) {

if (head == null) return false;

ListNode walker = head;

ListNode runner = head;

while (runner.next != null && runner.next.next != null) {

walker = walker.next;

runner = runner.next.next;

if (walker == runner) return true;

}

return false;

}

/**

public boolean hasCycle2(ListNode head) {

ListNode walker = head;

ListNode runner = head;

while (runner != null && runner.next != null) {

walker = walker.next;

runner = runner.next.next;

if (walker == runner) return true;

}

return false;

}

/**

/**

public ListNode detectCycle(ListNode head) {

ListNode slow = head;

ListNode fast = head;

while (fast != null && fast.next != null) {

fast = fast.next.next;

slow = slow.next;

if (fast == slow) {

ListNode slow2 = head;

while (slow2 != slow) {

slow = slow.next;

slow2 = slow2.next;

}

return slow;

}

}

return null;

}

/**

public ListNode detectCycle2(ListNode head) {

ListNode fast = head, slow = head;

while (true) {

if (fast == null || fast.next == null) return null;

fast = fast.next.next;

slow = slow.next;

if (fast == slow) break;

}

fast = head;

while (slow != fast) {

slow = slow.next;

fast = fast.next;

}

return fast;

}

/**

public ListNode detectCycle3(ListNode head) {

Set<ListNode> set = new HashSet<>();

while (head != null) {

if (set.contains(head)) {

return head;

} else {

set.add(head);

head = head.next;

}

}

return null;

}

/**

public ListNode detectCycle4(ListNode head) {

if (head == null) return null;

ListNode fast = head;

ListNode slow = head;

while (fast != null && fast.next != null) {

fast = fast.next.next;

slow = slow.next;

if (fast == slow) {

fast = head;

while (fast != slow) {

fast = fast.next;

slow = slow.next;

}

return slow;

}

}

return null;

}

/**

public ListNode reverseKGroup(ListNode head, int k) {

ListNode dummy = new ListNode(0);

dummy.next = head;

ListNode pre = dummy;

ListNode end = dummy;

while (end.next != null) {

for (int i = 0; i < k && end != null; i++) end = end.next;

if (end == null) break;

ListNode start = pre.next;

ListNode next = end.next;

end.next = null;

pre.next = reverse(start);

start.next = next;

pre = start;

end = pre;

}

return dummy.next;

}

private ListNode reverse(ListNode head) {

ListNode pre = null;

ListNode curr = head;

while (curr != null) {

ListNode next = curr.next;

curr.next = pre;

pre = curr;

curr = next;

}

return pre;

}

/**

public ListNode reverseKGroup2(ListNode head, int k) {

int n = 0;

for (ListNode i = head; i != null; n++, i = i.next) ;

ListNode dmy = new ListNode(0);

dmy.next = head;

for (ListNode prev = dmy, tail = head; n >= k; n -= k) {

for (int i = 1; i < k; i++) {

ListNode next = tail.next.next;

tail.next.next = prev.next;

prev.next = tail.next;

tail.next = next;

}

prev = tail;

tail = tail.next;

}

return dmy.next;

}

/**

public int[] twoSum(int[] nums, int target) {

int n = nums.length;

for (int i = 0; i < n; ++i) {

for (int j = i + 1; j < n; ++j) {

if (nums[i] + nums[j] == target) {

return new int[]{i, j};

}

}

}

return new int[0];

}

/**

public int[] twoSum2(int[] nums, int target) {

Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();

for (int i = 0; i < nums.length; ++i) {

if (hashtable.containsKey(target - nums[i])) {

return new int[]{hashtable.get(target - nums[i]), i};

}

hashtable.put(nums[i], i);

}

return new int[0];

}

/**

public int[] twoSum3(int[] nums, int target) {

int[] a = new int[2];

for (int i = 0; i < nums.length - 1; i++) {

for (int j = i + 1; j < nums.length; j++) {

if (nums[i] + nums[j] == target) {

a[0] = i;

a[1] = j;

return a;

}

}

}

return new int[0];

}

/**

public int maxArea(int[] height) {

int i = 0, j = height.length - 1, res = 0;

while (i < j) {

res = height[i] < height[j] ?

Math.max(res, (j - i) * height[i++]) :

Math.max(res, (j - i) * height[j--]);

}

return res;

}

/**

public int maxArea2(int[] height) {

int max = 0;

for (int i = 0, j = height.length - 1; i < j; ) {

int minHeight = height[i] < height[j] ? height[i++] : height[j--];

// int area = (j-i+1) * minHeight;

// max = Math.max(max , area);

max = Math.max(max, (j - i + 1) * minHeight);

}

return max;

}

/**

public int maxArea3(int[] height) {

int res = 0;

int i = 0;

int j = height.length - 1;

while (i < j) {

int area = (j - i) * Math.min(height[i], height[j]);

res = Math.max(res, area);

if (height[i] < height[j]) {

i++;

} else {

j--;

}

}

return res;

}

/**

public void moveZeroes(int[] nums) {

int j = 0;

for (int i = 0; i < nums.length; i++) {

if (nums[i] != 0) {

nums[j] = nums[i];

if (i != j) {

nums[i] = 0;

}

System.out.println("nums[" + i + "]=" + nums[i] + " nums[" + j + "]=" + nums[j]);

j++;

}

}

// 输出移动零后的数组

for (int i = 0; i < nums.length; i++) {

System.out.print("nums[" + i + "] = " + nums[i] + " ");

}

System.out.println();

}

public void moveZeroes2(int[] nums) {

for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.length; cur++) {

if (nums[cur] != 0) {

swap(nums[lastNonZeroFoundAt++], nums[cur]);

}

}

}

private void swap(int num, int num1) {

}

/**

public void moveZeroes3(int[] nums) {

if (nums == null || nums.length == 0)

return;

int index = 0;

//一次遍历，把非零的都往前挪

for (int i = 0; i < nums.length; i++) {

if (nums[i] != 0)

nums[index++] = nums[i];

}

//后面的都是0,

while (index < nums.length) {

nums[index++] = 0;

}

}

/**

public void moveZeroes4(int[] nums) {

int i = 0;//统计前面0的个数

for (int j = 0; j < nums.length; j++) {

if (nums[j] == 0) {//如果当前数字是0就不操作

i++;

} else if (i != 0) {

//否则，把当前数字放到最前面那个0的位置，然后再把

//当前位置设为0

nums[j - i] = nums[j];

nums[j] = 0;

}

}

}

public void moveZeroes5(int[] nums) {

int i = 0;

for (int j = 0; j < nums.length; j++) {

//只要不为0就往前挪

if (nums[j] != 0) {

//i指向的值和j指向的值交换

int temp = nums[i];

nums[i] = nums[j];

nums[j] = temp;

i++;

}

}

}

/**

public void moveZeroes6(int[] nums) {

if (nums == null || nums.length == 0) return;

int insertPos = 0;

for (int num : nums) {

if (num != 0) nums[insertPos++] = num;

}

while (insertPos < nums.length) {

nums[insertPos++] = 0;

}

}

/**

public void moveZeroes7(int[] nums) {

int snowBallSize = 0;

for (int i = 0; i < nums.length; i++) {

if (nums[i] == 0) {

snowBallSize++;

} else if (snowBallSize > 0) {

int t = nums[i];

nums[i] = 0;

nums[i - snowBallSize] = t;

}

}

}

/**

public int climbStairs(int n) {

// base cases

if (n <= 0) return 0;

if (n == 1) return 1;

if (n == 2) return 2;

int one_step_before = 2;

int two_steps_before = 1;

int all_ways = 0;

for (int i = 2; i < n; i++) {

all_ways = one_step_before + two_steps_before;

two_steps_before = one_step_before;

one_step_before = all_ways;

}

return all_ways;

}

/**

public int climbStairs2(int n) {

int a = 1, b = 1;

while (n-- > 0)

a = (b += a) - a;

return a;

}

public int climbStairs3(int n) {

if (n <= 2) {

return n;

}

int f1 = 1, f2 = 2, f3 = 3;

for (int i = 3; i <= n; i++) {

f3 = f1 + f2;

f1 = f2;

f2 = f3;

}

return f3;

}