Java教程

Leecode 206.反转链表(Java)

本文主要是介绍Leecode 206.反转链表(Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 

 

  想法: 1.设链表长度为n,如5,头节点head,则最后一个元素位置为head-1。      错误,发现行不通,此为链表非数组,存储位置不连续   2.设两个指针p,q,让p,q指向head,再让p指向head的下一个,若不为空,则交换pq(45321),接着q指向p,p指向p的下一个,若不为空则交换(43521),继续,直至p指向空,此时(43215),此时迭代了1次。迭代次数为链表的长度-1        错误,理解题意错了,不是要求反向排序,而是链接的箭头逆序   ----查看答案和思路,重新整理         迭代:

 

 

  设三指针,其中p指针所指是算法中欲指向的位置,s指针是作为中间变量给p指针挪动位置和反转,q指针起的作用是前进   初始:p指向null,s和q指向head 当q.next不为空时,令q=q.next(向前移);s.next=p(反转);p=s(p移动位置向前);s=q(s移动向前); 当q.next为空,说明已经到了最后一个元素,此时直接将s.next=p(反转);或者也可以将q.next=p,也可以反转,反正s和q此时都是指向最后一个元素  
 1 /**
 2 * Definition for singly-linked list.
 3 * public class ListNode {
 4 *     int val;
 5 *     ListNode next;
 6 *     ListNode() {}
 7 *     ListNode(int val) { this.val = val; }
 8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9 * }
10 */
11 class Solution {
12     public ListNode reverseList(ListNode head) {
13         ListNode p,s,q=new ListNode();
14         p = null;
15         s = head;
16         q =head;
17         while (q.next != null){
18             q = q.next;
19             s.next = p;
20             p = s;
21             s = q;
22         }
23         q.next = p;
24         head = s;
25     return head;
26     }
27 }

 

 

 

 

这篇关于Leecode 206.反转链表(Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!