链表模板总结

单链表：

public class ListNode {
  int val;
  ListNode next;
  ListNode (int val) {
    this.val = val;
  }
}

1、反转单链表

迭代：

方法1：

public ListNode reverseList(ListNode head) {
    if (head == null) {
         return null; 
    }

    ListNode preH = new ListNode(0);
    preH.next = head;
    ListNode preCur = head;
    ListNode cur = preCur.next;

    while (Cur != null) {
        preCur.next = Cur.next;
        Cur.next = preH.next;
        preH.next = Cur;
        Cur = preCur.next;
    }

    return preH.next;
}

方法2：

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

递归：

public class Solution {
    public ListNode reverseList(ListNode head) {
        //ListNode pre = null;
        return reverseNode(head, null);
    }
    
    private ListNode reverseNode (ListNode head, ListNode pre) {
        if (head == null) {
            return pre;
        }
        ListNode next = head.next;
        head.next = pre;
        //pre = head;
        return reverseNode(next, head);
    }
}

2、寻找单链表的中点

public ListNode findMid(ListNode head) {
  ListNode slow = head;
  ListNode fast = head;
  while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
  }
  return slow;
}