反转

  1. // 递归
  2. ListNode reverse(ListNode head) {
  3.         if (head == null || head.next == null)
  4.             return head;
  5.         ListNode newHead = reverse(head.next);
  6.         head.next.next = head;
  7.         head.next = null;
  8.         return newHead;
  9.     }
  11. // 迭代
  12. ListNode reverse(ListNode head) {
  13.         ListNode pre = null, cur = head;
  14.         while (cur != null) {
  15.             ListNode ne = cur.next;
  16.             cur.next = pre;
  17.             pre = cur;
  18.             cur = ne;
  19.         }
  20.         return pre;
  21.     }

寻找链表中间节点

如果是奇数个节点，返回最中间的一个即可
如果是偶数个节点，返回中间靠右或靠左的那个。

  1. //使用虚拟头节点，slow最终指向中间靠左的节点
  2. if (head == null || head.next == null) return;
  3. ListNode dummy = new ListNode(-1, head);
  4. ListNode fast = dummy, slow = dummy;
  5. do {
  6.     fast = fast.next.next;
  7.     slow = slow.next;
  8. } while (fast != null && fast.next != null);
  1. //不使用虚拟头节点，slow最终指向中间靠右的节点
  2. if (head == null || head.next == null)
  3.     return head;
  4. ListNode fast = head, slow = head;
  5. do {
  6.     fast = fast.next.next;
  7.     slow = slow.next;
  8. } while (fast != null && fast.next != null);

根据需求选择第一种或第二种写法！