链表和数组作为算法中的两个基本数据结构，在程序设计过程中经常用到。尽管两种结构都可以用来存储一系列的数据，但又各有各的特点。
数组的优劣势：可以方便的遍历查找需要的数据，时间复杂度为O(1)。这种时间上的便利性，是因为数组在内存中占用了连续的空间，在进行类似的查找或者遍历时，本质是指针在内存中的定向偏移。然而，当需要对数组成员进行添加和删除的操作时，数组内完成这类操作的时间复杂度则变成了O(n)
链表的优劣势：在某些操作上比数组更加高效，例如当进行插入和删除操作时，链表操作的时间复杂度仅为O(1)。因为链表在内存中不是连续存储的，所以可以充分利用内存中的碎片空间。
提到数组就不得不提到数组的排序：七种常见的数组排序算法整理(C语言版本)
- 下面主要针对leetcode上关于链表的一些题目，这里我是使用的JavaScript
function ListNode(val) {
this.val = val;
this.next = null;
}
一、3种方法实现反转链表
- 中文版地址:https://leetcode-cn.com/problems/reverse-linked-list/
-
1、递归实现
递归的方法其实是非常巧的，它利用递归走到链表的末端，然后再更新每一个node的next 值 ，实现链表的反转。而newhead 的值没有发生改变，为该链表的最后一个结点，所以，反转后，我们可以得到新链表的head。
var reverseList = function(head) {
if (!head || !head.next) return head;
let newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
};
-
2、新建链表，头节点插入法
新建一个头结点，遍历原链表，把每个节点用头结点插入到新建链表中。最后，新建的链表就是反转后的链表。
var reverseList = function(head) {
if (!head || !head.next) return head;
let lastNode = new ListNode(head.val), curNode;
let node = head.next;
while (node) {
curNode = new ListNode(node.val);
curNode.next = lastNode;
lastNode = curNode;
node = node.next;
}
return curNode;
};
-
3、直接反转
把当前链表的下一个节点指向当前结点，直至循环结束
var reverseList = function(head) {
if(!head || !head.next) return head
let pre = head, cur, last = head.next;
head.next = null;
while (last) {
cur = last;
last = cur.next;
cur.next = pre;
pre = cur;
}
return cur;
};
二 、两两交换链表中的节点
记录相邻两个结点cur和last，以及之前的结点prev，然后去进行反转相邻的两个结点，依次循环到最后
var swapPairs = function(head) {
if(!head || !head.next) return head
let res = head.next
let cur = head
let prev = last = null
while(cur && cur.next){
last = cur.next
cur.next = last.next
last.next = cur
if(prev) prev.next = last
prev = cur
cur = cur.next
}
return res
};
三、环形链表
正常链表都是有头有尾的，而环形链表则是没有尾的，它的尾会指向其中一个结点(不一定是指向头结点)，也就是环形链表，该题目就是来判断一个链表是否是环形链表。
正常来说，对链表进行循环，如果存在尾指针，即某结点指向null，即可证明该链表不是环形链表。但如果对环形链表进行循环的话，会造成死循环，这样就没办法确定是链表足够长还是该链表是环形链表。
- 1、比较容易想到的就是利用数组(或集合):循环链表，将结点依次保存在数组中，如果下个结点已经在数组中存在，则说明是环形链表。如果循环到最后指向null，则非环形链表。
var hasCycle = function(head) {
let nodes = []
while(head){
if(nodes.indexOf(head)) return true
nodes.push(head)
head = head.next
}
return false
};
- 2、还有一种比较巧妙的方法:快慢指针
快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。此外还有其他不少巧妙的应用。
//这里使用快慢指针，slow每次走一步，fast每次走两步，如果不是环形链表，则会一直循环下去，永远不会相遇，直至循环结束。
//反之如果这两个指针相遇，则说明该链表是环形链表。
var hasCycle = function(head) {
let slow = fast = head
while(fast && fast.next){
slow = slow.next
fast = fast.next.next
if(slow == fast) return true
}
return false
};
四、 环形链表 II
题目意思是如果链表是环形链表，就返回交点(链表尾连接到链表中的位置)在该链表中的位置，否则返回null
如果是用方法1使用数组保存结点，很容易就可以做到，这里不再赘述
快慢指针的话，首先先循环一次，判断是否是环形链表，不是的话直接返回null。是的话，则记录下相遇点。然后head开始跑，同时fast指针继续从相遇点跑，则head必然会和fast指针在环形链表交点相遇。
var detectCycle = function(head) {
let slow = fast = head
while(fast && fast.next){
slow = slow.next
fast = fast.next.next
if(slow == fast) {
while(fast != head){
head = head.next
fast = fast.next
}
return head
}
}
return null
};
网友评论