《剑指Offer》-03链表

发表于 | 分类于

从尾到头打印链表

题目描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function printListFromTailToHead(head)
{ 
    const stack=[];
    let node=head;
    while(node){
        stack.push(node.val);
        node=node.next;
    }
    return stack.reverse();    
}

第二种解法

1
2
3
4
5
6
7
8
9
function printListFromTailToHead(head) {
    // write code here
    var res = [], pNode = head;
    while (pNode != null) {
        res.unshift(pNode.val);
        pNode = pNode.next;
    }
    return res;
}

总结：
reverse 数组反转
unshift 可向数组的开头添加一个或更多元素，并返回新的长度。

链表中环入口结点

题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
    // write code here
    if(!pHead || !pHead.next ||!pHead.next.next){
        return null;
    }
    let fast=pHead.next.next,
        slow=pHead.next;
    while(fast){
        if(fast!==slow){
            fast=fast.next.next;
            slow=slow.next;
        }else{
            break;
        }
    }
    
    //判断有无环
    if(!fast){
        return null;
    }
    
    //找入环点
    fast=pHead;
    while(fast!==slow){
        fast=fast.next;
        slow=slow.next;
    }
    return fast;
}

总结：《漫画算法》详解，见P159

删除链表中重复的结点

题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function deleteDuplication(pHead)
{
    // write code here
    // write code here
    if(!pHead || !pHead.next){   //0结点1结点情况
        return pHead;
    }
    
    const Head=new ListNode(0);//考虑到如果第一个和第二个节点就相同了的情况，所以添加一个头结点
    Head.next=pHead;
    let pre =Head,
        cur =Head.next;
    while(cur){
        if(cur.next && cur.val===cur.next.val){
            // 找到最后的一个相同节点,因为相同节点可能重复多个
            while(cur.next && cur.val === cur.next.val){
                cur=cur.next;
            }
            pre.next=cur.next;//找到了不重复的之后跟pre连起来，就是用pre.next指向那个位置，也就是cur.next
            cur=cur.next;
        }else{
            pre=pre.next
            cur=cur.next;
        }
    }
    return Head.next;

}

相似题：LeetCode 83
删除排序链表中的重复元素——–注意这题重复元素会保留1

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。示例 1:输入: 1->1->2
输出: 1->2
示例 2:输入: 1->1->2->3->3
输出: 1->2->3

1
2
3
4
5
6
7
8
9
10
11
12
13
var deleteDuplicates = function(head) {
    let saveHead = head
    // 外层while控制循环完整个链表的长度
    while(head && head.next) {
        // 内层循环用于比较当前值是否和下一个值相等，相等则通过改变节点的指向来“删除”元素
        while(head.next && head.next.val === head.val) {
            head.next = head.next.next
        }
        // 移动head到下一个节点
        head = head.next
    }
    return saveHead
};
0%