206. 反转链表

步骤

反转区间[head,nil)，pre是前驱节点，cur是当前节点，next是后继节点。
1. 保存cur的后继节点到next。
2. pre设为cur的后继节点。
3. pre走到cur位置。
4. cur走到next位置。

Go代码

func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return head
	}

	var pre *ListNode = nil
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}

	return pre
}

Java代码

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

        ListNode pre = null;
        for (ListNode cur = head; cur != null; ) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
}

92. 反转链表 II

步骤

subHeadPre是待反转子链表首节点前驱，subHead是待反转子链表首节点。
subTail是待反转子链表尾节点，subTailNext是待反转子链表尾节点的后继节点。
1. 通过循环来获取subHeadPre、subHead、subTail和subTailNext。
2. 反转子链表，串连子链表到原链表中。
3. 根据left是否为1来决定首节点。

Java代码

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode subHeadPre = null;
        ListNode subHead = head;
        if (left > 1) {
            subHeadPre = getListNodeByIndex(head, left - 1);
            subHead = subHeadPre.next;
        }

        ListNode subTail = getListNodeByIndex(head, right);
        ListNode subTailNext = subTail.next;

        reverseListK(subHead, subTailNext);

        subHead.next = subTailNext;
        if (left > 1) {
            subHeadPre.next = subTail;
            return head;
        }
        return subTail;
    }

    public static ListNode getListNodeByIndex(ListNode head, int index) {
        for (int count = 1; head != null; count++, head = head.next) {
            if (count == index) {
                return head;
            }
        }

        return null;
    }

    public static ListNode reverseListK(ListNode head, ListNode tail) {
        ListNode pre = head;
        ListNode cur = head;

        for (; cur != tail; ) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
}

25. K个一组翻转链表

步骤

1. 循环遍历得到k个一组的子链表首尾，不足k就不需要反转。
2. 反转子链表。
3. 子链表原首节点指向下一个待反转子链表的新首节点。

Go代码

func reverseKGroup(head *ListNode, k int) *ListNode {
	if head == nil {
		return nil
	}

	a := head
	b := head
	for i := 0; i < k; i++ {
		if b == nil {
			return head
		}
		b = b.Next
	}

	kHead := reverseK(a, b)
	a.Next = reverseKGroup(b, k)
	return kHead
}

func reverseK(head, tail *ListNode) *ListNode {
	if head == nil {
		return nil
	}

	var pre *ListNode = nil
	cur := head
	for cur != tail {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}

	return pre
}

Java代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        ListNode subHead = head;
        ListNode subTail = head;
        for (int i = 0; i < k; i++) {
            if (subTail == null) {
                return subHead;
            }
            subTail = subTail.next;
        }

        ListNode kHead = reverseListK(subHead, subTail);
        subHead.next = reverseKGroup(subTail, k);

        return kHead;
    }

    public ListNode reverseListK(ListNode head, ListNode tail) {
        if (head == null) {
            return null;
        }

        ListNode pre = head;
        for (ListNode cur = head; cur != tail; ) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
}