[数据结构与算法]leetcode刷题之链表

链表题型

1、移除指定链表元素

使用虚拟头结点，不断Next，当val是目标值时，指向下一个

function removeNode(head, val) {
	const ret = new ListNode(0,head);
	let cur = ret;
	while(cur.next) {
		if(cur.next.val === val) {
			cur.next = cur.next.next;
			continue;
		}
		cur = cur.next;
	}
	return ret.next;
}

2、翻转链表

使用双指针法，定义当前指针cur和前一个指针pre，不断向后移动，记得先保存一下cur.next到tmp中，方便后续更新cur pre

function reverseListNode(head) {
	if(!head || !head.next) return head;
	let tmp = null, pre = null, cur = head;
	while(cur) {
		tmp = cur.next;// 保存一下 cur的下一个节点，因为接下来要改变cur->next
		cur.next = pre;// 翻转操作
		pre = cur;// 更新pre 和 cur指针
		cur = tmp;
	}
	return pre;
}

3、两两交换链表中的节点

使用添加虚拟节点，不断while循环交换节点
ret — 1 — 2 —3 — 4 — …
ret — 2 — 1 — 3 — 4 — …

var swapPairs = function(head) {
    const ret = new ListNode(0, head);
    let tmp = ret;
    while (tmp.next && tmp.next.next) {
        let cur = tmp.next.next, pre = tmp.next;
        pre.next = cur.next;
        cur.next = pre;
        tmp.next = cur;
        tmp = pre;

    }
    return ret.next;
};

4、删除链表中的第n个节点

使用快慢指针 fast slow +虚拟头节点方法，将slow指向要删除的节点，删掉

var removeNthFromEnd = function(head, n) {
    let ret = new ListNode(0, head), fast = slow = ret;
    while(n--) fast = fast.next;
    while(fast.next !== null) {
		fast = fast.next;
		slow = slow.next;
	}
	slow.next = slow.next.next;
	return ret.next;
};

5、链表相交

如果不使用getListLen函数来获取链表长度，而是通过 curA curB来获取的话，不断while循环，curA curB不断向后移动，但是要在lenA < lenB之前，把curA curB重新指向headA headB

var getListLen = function(head) {
    let len = 0, cur = head;
    while(cur) {
       len++;
       cur = cur.next;
    }
    return len;
}
var getIntersectionNode = function(headA, headB) {
    let curA = headA,curB = headB,
        lenA = getListLen(headA),
        lenB = getListLen(headB);
    if(lenA < lenB) {
        // 下面交换变量注意加 “分号” ，两个数组交换变量在同一个作用域下时
        // 如果不加分号，下面两条代码等同于一条代码: [curA, curB] = [lenB, lenA]
        [curA, curB] = [curB, curA];
        [lenA, lenB] = [lenB, lenA];
    }
    let i = lenA - lenB;
    while(i-- > 0) {
        curA = curA.next;
    }
    while(curA && curA !== curB) {
        curA = curA.next;
        curB = curB.next;
    }
    return curA;
};

var getIntersectionNode = function(headA, headB) {
    let lenA = lenB = 0;
    let curA = headA, curB = headB;
    while(curA) {
        lenA++;
        curA = curA.next;
    }
    while(curB) {
        lenB++;
        curB = curB.next;
    }
    curA = headA;
    curB = headB;

    if(lenB > lenA) {
        [curA, curB] = [curB, curA];
        [lenA, lenB] = [lenB, lenA];
    }

    let i = lenA - lenB;
    while(i-- > 0) {
        curA = curA.next;
    }

    while(curA && curA !== curB) {
        curA = curA.next;
        curB = curB.next;
    }
    return curA;
};