[数据结构与算法]LeetCode206:反转单链表

序言

这个博客讲解简单的链表反转，主要同过OJ来进行测试，题目简单，思想很重要,这里的pHead和head一样，抱歉不太严谨。

题目来源

力扣： 206 反转链表
牛客网：NC78 反转链表

解法

第一步：判断是不是空节点

if (pHead == NULL)
{
		printf("是空节点\n");
		return NULL;
}

第二步：画图分析

我们定义两个变量，其中cur 指向第二个节点（假如不是单节点）

    struct Node* cur = pHead->next;
	struct Node* helper = NULL;
	pHead->next = NULL;//将头节点的next置为空指针

我们开始一步一步来

• pHead依次在移动，紧临cur
• 记住下一个节点的位置很重要，这就是helper的作用

从这开始我们一步一步的走，是一个循环，我们要知道循环条件

解析

1. helper指向了NULL
2. cur.next指向前一个节点的地址
3. pHead移动到了原始的尾节点
4. cur指向NULL，所以所有工作完成，不在循环

完整代码

C语言

struct Node
{
	int data;
	struct Node* next;
};

//反转列表
struct Node* ReverseList(struct Node* pHead) 
{
	// write code here
	//第一步 ： 判断野指针
	if (pHead == NULL)
	{
		printf("是空节点\n");
		return NULL;
	}
	struct Node* cur = pHead->next;
	struct Node* helper = NULL;
	pHead->next = NULL;
	while (cur != NULL)
	{
		helper = cur->next;
		cur->next = pHead;
		pHead = cur;
		cur = helper;
	}
	return pHead;
}

Java

class Node {
    public int data;
    public  Node next;
}
class Solution {
    public Node reverseList(Node head) {

        if(head == null) {
           return null;
        }

        Node helper = null;
        Node cur = head.next;
        head.next = null;
        while(cur != null) {

            helper = cur.next;
            cur.next = head;
            head = cur;
            cur = helper;
        }
        return head;
    }
}