算法：数组和链表-实战
实战的题目都是leetcode的题。
leetcode:206.反转一个单链表
给的初始链表类如下
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}第一种做法，迭代
时间复杂度O(n)
//迭代 时间复杂度O(n)
public ListNode reverseList(ListNode head) {
ListNode prev = null; //保存当前节点，反转时的下一节点
ListNode curr = head; //保存开始循环 ，当前节点。
while (curr != null) { //当前节点不为空 ，说明需要反转
ListNode nextTemp = curr.next; //保存当前节点 原下一节点。
curr.next = prev; //反转，当前节点 为上一节点
prev = curr; //保存下一个节点的 反转的上节点
curr = nextTemp; //循环下一节点。
}
return prev; //返回最后一节点
}第二种做法，递归
public ListNode reverselist2(ListNode head) {
if (head == null || head.next == null) return head; //递归出口
ListNode next = reverselist2(head.next); //递归，一直到递归出口
head.next.next = head; //开始处理子问题
head.next = null; //递归最后一步的节点指向
return next;
}第三种做法
先看，觉得是什么方法？递归/迭代？？
ListNode node = null;
public ListNode reverseList3(ListNode head) {
if(head == null) return null;
ListNode cur = new ListNode(head.val);
cur.next = node;
node = cur;
reverseList3(head.next);
return node;
}这个递归不是找到最后一个，也不是返回解决子问题的做法。
而是每一步都反转一个数，并合成在上一个。更像是迭代的样子！
leetcode:24.两两交换链表中的节点
解题思路
因为只是两两的交换，那么我们把第一二位作为一个整体，每次迭代都同时处理两个。一次迭代需要重新指向多少次呢？
即：内部交换 3->4的下一位(反转)，4->3(反转)， 那么谁指向4呢？？ 是1 吧， 那么 3->4的下一位(反转)是没有意义的（1->2的下一位），所以 我们需要 三个节点， 当前节点（3） 、当前节点的下一节点（4） 、 当前节点的上一节点（1）。
第一种做法，迭代
public ListNode swapPairs(ListNode head) {
ListNode pre = new ListNode(0);//存入对象
pre.next = head;//初始指向
ListNode temp = pre;//每次循环，引用的初始值，第一个节点为head、第二次为head.next、第三次为head.next.next.next。
while (temp.next != null && temp.next.next != null) {//传入三个对象，temp、temp.next、temp.next.next
ListNode a = temp.next;//备份第二个对象
ListNode b = temp.next.next;//备份第三个对象
a.next = b.next;//改变第二个对象的下一个对象引用 ，引用第三个对象的下一个
b.next = a;//改变第三个对象的下一个引用，引用第二个
temp.next = b;//第一个对象 指向 第二个b /也相当于保存对象到pre中，并把下一位的正确指向告诉pre
temp = a;//改变第一个对象引用 ，第三个a
}
return pre.next;
}第二种做法，递归
//递归
public ListNode swapPairs2(ListNode head) {
if (head ==null || head.next ==null) return head; //递归出口
ListNode next = head.next; //
head.next = swapPairs2(head.next.next);
next.next = head;
return next;
}leetcode:141环形链表
这个比较简单， 就是找链表是否为空， 空就不循环，反之。
第一种做法，硬做
//硬做
public boolean hasCycle1(ListNode head) {
int i = 0;
while (head != null) {
head = head.next;
i++;
if (i > 10000) {
return true;
}
}
return false;
}第二种做法，利用set集合
public boolean hasCycle3(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<ListNode>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}第三种做法，快慢指针
每次循环，一个指向下一个 、 一个指向下下一个。链表不循环的话，前面一个是追不上后面一个的。
//快慢指针
public boolean hasCycle2(ListNode head) {
if(head == null){
return false;
}
ListNode min = head;
ListNode max = head.next;
while (max != null && max.next != null) {
if (min == max) {
return true;
}
min = min.next;
max = max.next.next;
}
return false;
}leetcode的206题、24题、141题 就讲解完成了。有关数组和链表的理论知识可以访问这个。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-07-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录