单向链表的反转
程序员文章站
2024-03-21 14:49:16
...
遍历法
static Node reverse(Node head){
if(head == null){
return null;
}
Node pre = head;
Node cur = head;
Node reHead = null;
//如果当前节点为空结束循环
while(cur != null){
//保存下一个节点以免丢失
Node temp = cur.next;
//1.对pre和cur结点的关系进行反转。本来是pre指向cur的,用下面这条代码能够把cur指向pre。
cur.next = pre;
//2.如果下一个结点为空,那他就是反转链表的头结点
if(temp == null)
rehead = cur;
//上一个节点已经反转完成,现在要移动到下一个节点。
pre = cur;
cur = temp;
return rehead;
}
}
//简化版
static Node reverse(Node head){
Node pre = null;
Node cur = null;
while(head != null){
temp = head.next;
head.next = pre;
pre = head;
head = temp;
}
return pre;
}
递归
static Node reverse(Node head){
//我们从原链表的头结点开始
Node cur = head;
//递归到原链表的尾节点结束。递归到了尾节点的时候就返回当前节点
if(cur == null || cur.next == null){
return cur;
}else{
Node reHead = reverse(cur.next);
cur.next.next = cur;
cur.next = null;
return reHead;
}
}
内置法
LinkedList没有提供反转链表的相关函数,以下是通过foreach实现链表反转
static LinkedList reverse(LinkedList linkedList) {
LinkedList<Object> newLinkedList = new LinkedList<>();
for (Object object : linkedList) {
newLinkedList.add(0, object);
}
return newLinkedList;
}
上一篇: 前端新电脑配置
下一篇: grails 初体验