2021-11-24 第15天（加入队员 -> 14人）

付有杰：https://leetcode-cn.com/u/fuyoujie2020/
练习内容：翻转链表

```
public ListNode reverseList(ListNode head) {
        //迭代
        if (head == null){
            return null;
        }
        ListNode d = new ListNode(-1);
        d.next = head;
        ListNode pre = null;
        ListNode cur = head;
        /*
         定义cur 游标 定位需要翻转的节点，将节点的next指针指向前一个。
         翻转完成的条件：因为不知道尾部节点是多少，所以 cur = null 就是翻转完毕
         pre 此时就是最后的节点
         
         */
        while (cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return d.next;
    }
```

```
 public ListNode reverseList(ListNode head) {
        if (head == null){
            return null;
        }
         /*
         头插法：
         假设链表是1 2 3
         那么开始遍历：
         将2插入到1前面，游标右移
         2 1 3
         将3插入到2前面 游标右移
         3 2 1
         此时链表就反转了
         */
        //哑巴节点
        ListNode d = new ListNode(-1);
        //防止头引用丢失 d.next = 1
        d.next = head;
        // 对应例子的数字2
        ListNode cur = head.next;
        //提前将1.next = 2断开 否则后面2.next=1 会导致循环
        head.next = null;
        while (cur != null){
            // cur.next = 3
            ListNode next = cur.next;
            // 2.next = -1.next = 1;
            cur.next = d.next;
            // -1.next = 2
            //此时 链表是 -1 ——>2-> 1-> 3
            d.next = cur;
            cur = next;
        }
        // -1  3 2 1
        // return -1.next 就是 3 2 1
        return d.next;
    }
```

```
//简单递归
public ListNode reverseList(ListNode head){
        if (head == null){
            return null;
        }
        return reverseList(null,head);
    }

private ListNode reverseList( ListNode preNode, final ListNode cur) {
        if (cur == null){
            return preNode;
        }
        ListNode next = cur.next;
        cur.next = preNode;
        return reverseList(cur,next);
    }
```

算法小学妹/算法打卡

内容风险标识

评论 (14)