反转链表

1. 题目描述

输入一个链表，反转链表后，输出新链表的表头。

2. 思路

• 第一种：使用栈存储，然后pop构造链表
• 第二种：三指针

3. 实现

3.1. 栈

• java

public class 反转链表
{
    public ListNode ReverseList(ListNode head)
    {
        //检查参数
        if (head == null)
        {
            return null;
        }

        //遍历链表，放入stack中
        LinkedList<ListNode> stack = new LinkedList<>();
        ListNode current = head;
        while (current != null)
        {
            stack.add(current);
            current = current.next;
        }

        //不停得pop，构造链表
        ListNode newHead = stack.removeLast();
        ListNode now = newHead;
        while (!stack.isEmpty())
        {
            now.next = stack.removeLast();
            now = now.next;
        }
        now.next = null;

        return newHead;
    }
}

• go

// 先用栈存储，然后pop出来修改指针
// 时间：O（n）
// 空间：O（n）
func ReverseList(pHead *ListNode) *ListNode {
	if pHead == nil {
		return nil
	}

	nodes := make([]*ListNode, 0)
	n := pHead
	for n != nil {
		nodes = append(nodes, n)
		n = n.Next
	}

	newHead := nodes[len(nodes)-1]
	for i := len(nodes) - 1; i > 0; i-- {
		nodes[i].Next = nodes[i-1]
	}
	nodes[0].Next = nil

	return newHead
}

3.2. 三指针

• java

public class 反转链表2
{
    public ListNode ReverseList(ListNode head)
    {
        //检查参数
        if (head == null)
        {
            return null;
        }

        //三个指针分别指向前一个节点、当前节点、下一个节点
        ListNode prev = null;
        ListNode current = head;
        ListNode next = current.next;
        //prev  current next
        //1   ->  2   ->  3   ->  4   ->  5   ->  6
        while (current != null)
        {
            current.next = prev;
            prev = current;
            current = next;
            if (current != null)
            {
                next = current.next;
            }
        }

        return prev;
    }
}

• go

// 三指针
// 时间：O（n）
// 空间：O（1）
func ReverseList2(pHead *ListNode) *ListNode {
	if pHead == nil {
		return nil
	}
	var pre *ListNode
	now := pHead
	next := pHead.Next

	for now != nil {
		now.Next = pre
		pre = now
		now = next
		if next != nil {
			next = next.Next
		}
	}

	return pre
}

4. 参考

• 反转链表_牛客网
• 206. 反转链表 - 力扣（LeetCode）