# 数据结构基础之掌握5个常见的链表操作

### 常见的链表操作

• 单链表反转

• 链表中环的检测

• 两个有序的链表合并

• 删除链表倒数第 n 个结点

• 求链表的中间结点

leetcode 对应题号：206，141，21，19，876

### 单链表反转

/**
* @return {ListNode}
*/

let pre = null;

while(cur){
let next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre
};


### 链表中环的检测

/**
* @return {boolean}
*/
while(cur){
if(cur.val === 'cycleFlag'){
return true
}
cur.val = 'cycleFlag'
cur = cur.next
}
return false
};


var hasCycle = function(head) {
while(fast !== slow){
if(!fast || !fast.next)return false
fast = fast.next.next
slow = slow.next
}
return true
};


var hasCycle = function(head) {
try{
return false;
}
catch(err){
return true;
}
};


### 两个有序的链表合并

// 普通方法，遍历合并
var mergeTwoLists = function(l1,l2) {
if(l1 === null)return l2
if(l2 === null)return l1
while(l1 && l2){
if(l1.val <= l2.val){
node.next = l1
l1 = l1.next
}else{
node.next = l2
l2 = l2.next
}
node = node.next
}
node.next = l1?l1:l2
};

// 递归合并
var mergeTwoLists = function(l1,l2) {
if(l1 === null)return l2
if(l2 === null)return l1

if(l1.val <= l2.val){
l1.next = mergeTwoLists(l1.next,l2)
return l1
}
l2.next = mergeTwoLists(l1,l2.next)
return l2
}


### 删除链表倒数第 n 个结点

var removeNthFromEnd = function(head, n) {
let p = new ListNode(-1)
let a = p
let b = p
while(n > 0){
b = b.next
n--;
}

while(b.next !== null){
a = a.next
b = b.next
}

a.next = a.next.next
return p.next
};


### 求链表的中间结点

var middleNode = function(head) {
};