206. 反转链表

  1.  /**
  2.      * while循环
  3.      *
  4.      * @param head
  5.      * @return
  6.      */
  7.     public static ListNode whileLoop(ListNode head) {
  8.         if (head == null) {
  9.             return head;
  10.         }
  11.         ListNode pre = null;
  12.         ListNode cur = head;
  13.         while (cur != null) {
  14.             ListNode tmp = cur.next;
  15.             cur.next = pre;
  16.             pre = cur;
  17.             cur = tmp;
  19.         }
  20.         return pre;
  21.     }
 /**
     * 递归
     *
     * @param head
     * @return
     */
    public static ListNode recursive(ListNode head) {
        if (head == null) {
            return head;
        }
        return recursiveSub(null, head);
    }

    public static ListNode recursiveSub(ListNode pre, ListNode cur) {
        if (cur == null) {
            return pre;
        }
        ListNode tmp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = tmp;
        return recursiveSub(pre, cur);
    }

92. 反转链表 II

结题思路：

  1. 定位到反转部分的前驱节点和后驱节点。

(遍历到left的前一个位置，因为需要遍历每一个位置，所以创建一个虚拟头结点)

  1. 进行反转。

(preL指向l的上一个节点，rPost指向r的下一个节点)

  1. 反转后，前驱节点链接到反转后的头节点，后驱节点链接尾节点。

( preL.next = r; l.next = rPost; ) image.png

    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left>=right){
            return head;
        }

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        head = dummy;

        for (int i = 1; i < left; i++) {
            head = head.next;
        }
        ListNode preL = head;
        ListNode l = head.next;
        ListNode r = l;
        ListNode rPost = r.next;
        for (int i = left; i < right; i++) {
            ListNode tmp = rPost.next;
            rPost.next = r;
            r = rPost;
            rPost = tmp;
        }
        preL.next = r;
        l.next = rPost;
        return dummy.next;
    }