LeetCode 206.翻转链表
程序员文章站
2024-03-22 15:05:10
...
LeetCode 206.翻转链表
题目:
- 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
解题思路
解法一:
用最简单的方法实现链表的翻转,只需要逐个将链表的结点从原链表中“拿”出来,然后用前插法将它添加至新链表即可。
具体实现:
先判断链表是否为空,如果是空,直接返回head;
如果不为空,就开始翻转。
由于head链表头结点也有元素,所以要先将头结点中的元素添加至新链表后。然后通过循环将head链表中的结点逐个拿走,添加至新链表。
解法二: 迭代
使每个结点的next指向前结点。
具体实现:
定义两个指针,分别指向当前结点(cur)和当前结点的前一结点(pre),然后令head指向下一节点。
将pre赋给cur.next,然后这三个指针整体前进一个结点(类似滑动窗口)。循环执行,最后返回pre即可。
代码
解法一
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head!=null) {
ListNode p=new ListNode(0);
ListNode q=new ListNode(head.val);
q.next=null;
p.next=q;
while(head.next!=null) {
ListNode s=head.next;//创建指针,指向原链表的下一节点,用于构建新链表
head.next=head.next.next;//删除其后的一个结点
s.next=p.next;//将原链表逐个前插至新链表
p.next=s;
}
return p.next;
}
else
return head;
}
}
解法二
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
//迭代实现让当前的结点next指向前结点
ListNode pre=null;
ListNode cur=head;
while(head!=null) {
head=head.next;
cur.next=pre;
pre=cur;cur=head;
}
return pre;
}
}
上一篇: 带头结点的单向链表 增删改查遍历
下一篇: 多客户端之间的通信(模拟聊天室)
推荐阅读