经典面试题：反转链表_面试链表反转

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

　链表结点定义如下，这里使用的是C#描述：
　

public class Node
    {
        public int Data { get; set; }
        // 指向后一个节点
        public Node Next { get; set; }

        public Node(int data)
        {
            this.Data = data;
        }

        public Node(int data, Node next)
        {
            this.Data = data;
            this.Next = next;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

定义3个指针，分别指向当前遍历到的结点、它的前一个结点及后一个结点。在遍历过程中，首先记录当前节点的后一个节点，然后将当前节点的后一个节点指向前一个节点，其次前一个节点再指向当前节点，最后再将当前节点指向最初记录的后一个节点，如此反复，直到当前节点的后一个节点为NULL时，则代表当前节点时反转后的头结点了。

　　整个过程只需遍历链表一次，效率提高不少，且需要的外部空间也较第一种方法要少很多，实现代码如下：

public static Node ReverseList2(Node head)
    {
        if (head == null)
        {
            return null;
        }

        Node reverseHead = null;
        // 指针1：当前节点
        Node currentNode = head;
        // 指针2：当前节点的前一个节点
        Node prevNode = null;

        while(currentNode != null)
        {
            // 指针3：当前节点的后一个节点
            Node nextNode = currentNode.Next;
            if(nextNode == null)
            {
                reverseHead = currentNode;
            }
            // 将当前节点的后一个节点指向前一个节点
            currentNode.Next = prevNode;
            // 将前一个节点指向当前节点
            prevNode = currentNode;
            // 将当前节点指向后一个节点
            currentNode = nextNode;
        }

        return reverseHead;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

原文地址：
https://www.cnblogs.com/edisonchou/p/4769537.html