题目
实现单链表的逆转函数,输入一个链表,反转链表后,返回翻转之后的链表。
分析
利用三个指针:head,node,nodeNext
node指向当前结点;
head指向当前结点的前一个结点;
nodeNext指向当前结点的后一个结点。
-
先将head的next指向null;
-
将head结点与node结点反转,并设置head,node与nodeNext的新位置;:
nodeNext = node.next;
node.next = head;
head = node;
node = nodeNext
-
循环2的过程,直到node指向null,此时链表反转结束,head指向新链表的头结点。
思路如下图所示:
代码
/*
只需要完成逆置链表函数
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
//要用到三个指针,当前结点的前一个结点head,当前结点node,当前结点的后一个结点nodeNext
if(head == null){
return null;
}
ListNode node = head.next;
//先将第一个结点和第二个结点反转
head.next = null;
while(node != null){
ListNode nodeNext = node.next;
node.next = head;
head = node;
node = nodeNext;
}
return head; //当node为null时,反转结束,此时的head即为新链表的头结点,返回头结点head
}
}
运行结果