欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 206.翻转链表

程序员文章站 2024-03-22 15:05:10
...

LeetCode 206.翻转链表

题目:

  1. 反转链表
    反转一个单链表。

示例:

输入: 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;
    }
}
相关标签: 数据结构