反转链表

前言

近期小伙伴群里各种反转链表题目，你说这个算法，嗯~ 还挺有意思的！

我也来做一做吧！

1

反转单链表

解题思路

使用两个临时变量，分别标记反转过程中的两个链表的头。

class Solution {
    public ListNode reverseList(ListNode head) {

        if (head == null || head.next == null) {
                return head;
            }

            ListNode temp;
            ListNode newHead = null;

            while (head != null) {

                temp = head.next;
                head.next = newHead;
                newHead = head;
                head = temp;

            }

            return newHead;

    }
}

我也就虐虐这种 Easy 的。

2

反转 m 到 n 的链表

解题思路

1. 先定位到 left 和 leftPrev 节点
2. 反转
3. 结束

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
            
        if (left == right) {
            return head;
        }

        // 第一个节点位置是
        ListNode tempHead = new ListNode(-1, head);

        ListNode prevNode = tempHead;

        // 上一个节点, 节点从 1 开始计数
        for (int i = 1; i < left; i++) {
            prevNode = prevNode.next;
        }

        ListNode cur = prevNode.next;
        // left 位置的节点
        ListNode leftNode = prevNode.next;
        ListNode temp;

        // 反转
        for (int i = left; i <= right; i++) {
            leftNode.next = cur.next;
            temp = cur.next;

            cur.next = prevNode.next;
            prevNode.next = cur;
            cur = temp;

        }
        return tempHead.next;
    }
}

3

K 个一组翻转链表

还有！一个链表翻来翻去 ……