算法与数据结构

题目描述

给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。

如当输入链表{1,2,3}时，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

思路 & 解答

循环反向指针

首先，使用循环解答，不断把指向下一个的指针，指向前面的。假设链表是1->2->3->4，那么执行一次循环里面的内容的图示如下：

直到 head==null 的时候，返回first即可。代码如下：

    public static ListNode ReverseList(ListNode head) {
        if (head == null) {
            return head;
        } else {
            ListNode first = null;
            while (head!= null) {
                ListNode temp = head.next;
                head.next = first;
                first = head;
                head = temp;
            }
            return first;
        }
    }

C++ 代码如下：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode *ReverseList(ListNode *pHead) {
        if (pHead == NULL) {
            return pHead;
        } else {
            ListNode *first = NULL;
            while (pHead != NULL) {
                ListNode *temp = pHead->next;
                pHead->next = first;
                first = pHead;
                pHead = temp;
            }
            return first;
        }
    }
};

时间复杂度：O(n) 空间复杂度：O(1)

头插法

还有一种方法，是头插法，也就是先初始化一个 listNode,初始化为 0->null；然后遍历链表，不断将元素插入到0的后面。假设链表是 1->2->3->4.

0 -> 1 -> null
0 -> 2 -> 1 -> null
0 -> 3 -> 2 -> 1 -> null
0 -> 4 -> 3 -> 2 -> 1 -> null

然后取出 listnode.next 即可。

代码如下：

public ListNode ReverseList(ListNode head) {
    ListNode listnode = new ListNode(1);
    while (head != null) {
        ListNode next = head.next;
        head.next = listnode.next;
        listnode.next = head;
        head = next;
    }
    return listnode.next;
}

C++代码实现如下：

class Solution {
public:
    ListNode *ReverseList(ListNode *pHead) {
        ListNode *listnode = new ListNode(1);
        while (pHead != NULL) {
            ListNode *next = pHead->next;
            pHead->next = listnode->next;
            listnode->next = pHead;
            pHead = next;
        }
        return listnode->next;
    }
};

时间复杂度：O(n) 空间复杂度：O(1)