算法 - 链表实现(OC) 及简单的链表算法

链表实现

LinkNode.h文件 链表类  .m文件什么都不用写
@interface LinkNode : NSObject
@property (nonatomic, assign) int val;
@property (nonatomic, strong, nullable) LinkNode *next;
@end

链表实现
+ (LinkNode*)arrayTransforLink:(NSArray *)array{
    LinkNode *node = [LinkNode new],*p = [LinkNode new];
    p.val = [array[0] intValue];
    node.next = p;
    for (int i = 1; i<array.count; i++) {
        LinkNode *nextNode = [LinkNode new];
        nextNode.val = [array[i] intValue];
        p.next = nextNode;
        p = p.next;
    }
    node = node.next;//删除无用头结点
    return node;
}
//实现一个链表
LinkNode *node = [LinkTool arrayTransforLink:@[@1,@2,@3,@5]];

打印链表

+ (void)printNode:(LinkNode *)node{
    while (node) {
        NSLog(@"%d",node.val);
        node = node.next;
    }
}

链表反转 (使用递归法)

//反转
+(LinkNode*)reversalLink:(LinkNode *)node{
    LinkNode *p , *q, *t=node;
    while (t) {
        p = t;//浅拷贝
        t = t.next;
        p.next = q;
        q = p;
    }
    
    return q;
}

两个有序链表合并为一个有序链表

力扣题
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

+ (LinkNode*)merge:(LinkNode *)node link:(LinkNode*)link{

    LinkNode *selfNode = link;    
    LinkNode *newNode = [LinkNode new];//记录
    LinkNode *headNode = newNode;//头链表
    while (selfNode&&node) {
        if (selfNode.val < node.val) {
            newNode.val = selfNode.val;
            
            selfNode = selfNode.next;
        }else{
            newNode.val = node.val;
            
            node = node.next;
        }
        newNode.next = [LinkNode new];
        newNode = newNode.next;
    }
    LinkNode *p = selfNode?selfNode:node;
    newNode.val = p.val;
    return headNode;
}

链表 两数相加 （简单的中等难度）

力扣题 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

实例一
输入：l1 = [2,4,3], l2 = [5,6,4] 
输出：[7,0,8]
解释：342 + 465 = 807.
实例二：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

思路：

1. 遍历两个链表获得两个整数
2. 两个整数相加
3. 获得总数后整数转链表

缺点：当链表节点很多的时候会崩掉
如：

[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
[5,6,4]

// 整数转链表
+ (LinkNode*)intTransforLink:(int)number{
    LinkNode *node = [LinkNode new],*p = [LinkNode new];
    node.next = p;
    if (number<10) {
        node.val = number;
        return node;
    }
    while (number) {
        int index = number%10;
        LinkNode *nextNode = [LinkNode new];
        nextNode.val = index;
        p.next = nextNode;
        p = p.next;
        number = number/10;
    }
     
    node = node.next;//删除无用头结点
    node = node.next;//删除无用头结点
    return node;
}

//实现代码
    LinkNode *node = [LinkTool arrayTransforLink:@[@9,@9,@9,@9,@9,@9,@9]];
    LinkNode *node1 = [LinkTool arrayTransforLink:@[@9,@9,@9,@9]];
    double nodeValue = 0,node1Value = 0;
    int times = 1;
    while (node||node1) {
        nodeValue = node.val*times + nodeValue;
        node = node.next;
        node1Value = node1.val*times + node1Value;
        node1 = node1.next;
        times*=10;
    } 
    int totle = nodeValue + node1Value;
    LinkNode *totleLink = [LinkTool intTransforLink:totle];
    [LinkTool printNode:totleLink];

思路二：

1. 遍历每一个节点
2. 两个节点和进位相加
3. 是否超过10，超过则进位1不超过则进位0
4. 子节点的创建依赖于两个节点其中是否有子节点
5. 每次判断其中一个节点是否为空。如果其中一个节点为空则判断进位是否为0 ，进位为0则直接赋值不为空的节点
6. 遍历完后查看进位是否为0 不为0则增加一个子节点 储存进位

 + (LinkNode*)addTwoNumbers:(LinkNode *)node link:(LinkNode *)node1{
    LinkNode *totleNode = [LinkNode new],*p = [LinkNode new];
    totleNode.next = p;
    int number = 0;
    
    while (node||node1) {
        if (!node && number == 0) {
            p.val = node1.val;
            p.next = node1.next;
            break;
        }
        if (!node1 && number == 0) {
            p.val = node.val;
            p.next = node.next;
            break;
        }
        int totleValue = node.val+node1.val +number;
        number = totleValue/10;
        totleValue = totleValue%10;
        p.val = totleValue;
        
        node = node.next;
        node1 = node1.next;
        if (node||node1) {
            p.next = [LinkNode new];
            p = p.next;
        }
    }
    if (number) {//判断最后面是否有进位
        p.next = [LinkNode new];
        p = p.next;
        p.val = number;
    }
    totleNode = totleNode.next;//移除无用头结点
    return totleNode;
}

swift代码

func addTwoNumbers(l1:LinkNode?,l2:LinkNode?) -> LinkNode {
    var node1 = l1
    var node2 = l2
     
    var totleNode = LinkNode.init(),p = LinkNode.init()
    totleNode.next = p

    var number = 0
    while ((node1 != nil)||(node2 != nil)) { 
        var totleValue = number
        if node1 != nil {
            totleValue = totleValue + node1!.val
        }else if(number == 0){
            p.val = node2!.val
            p.next = node2?.next
            break
        }
        if node2 != nil {
            totleValue = totleValue + node2!.val
        }else if(number == 0){
            p.val = node1!.val
            p.next = node1?.next
            break
        }
        number = totleValue/10
        totleValue = totleValue%10
        p.val = totleValue
        
        node1 = node1?.next
        node2 = node2?.next
        if ((node1 != nil)||(node2 != nil)) {
            p.next = LinkNode.init()
            p = p.next!
        }
    }
    
    if number != 0 {
        p.next = LinkNode.init()
        p = p.next!
        p.val = number
    }
    totleNode = totleNode.next!
    
    return totleNode
}