数据结构与算法之链表面试题(四)

2019-04-29 本文已影响13人路飞_Luck

一删除链表中的节点

237. 删除链表中的节点

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

说明:

链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

实例代码如下

- (id)remove:(NSUInteger)index {
    LinkNode *node = _first;
    if (index == 0) {
        _first = _first.next;
    } else {
        LinkNode *prev = [self node:index - 1];
        node = prev.next;
        prev.next = node.next;
    }
    self.size--;
    return node.element;
}

运行结果如下：

image.png

二反转一个链表

206. 反转链表

示例：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

请分别用迭代（非递归）或递归两种方式实现

公共代码说明

链表节点输出打印

- (NSString *)description {
    [super description];
    NSMutableString *strM = [NSMutableString string];
    [strM appendString:[NSString stringWithFormat:@"[%@",self.element]];
    
    LinkNode *node = self;
    while (node.next) {
        node = node.next;
        [strM appendString:[NSString stringWithFormat:@",%@",node.element]];
    }
    
    [strM appendFormat:@"]"];
    return strM.copy;
}

生成链表

LinkedList *list = [[LinkedList alloc] init];
self.list = list;
[list add:@1];
[list add:@2];
[list add:@3];
[list add:@4];
[list add:@5];
NSLog(@"%@",list.description);

递归实现实例代码如下

// 递归反转链表
- (LinkNode *)reverseList:(LinkNode *)head {
    if (head == nil || head.next == nil) {
        return head;
    }
    
    // 递归实现
    LinkNode *newHead = [self reverseList:head.next];
    head.next.next = head;
    head.next = nil;
    return newHead;
}

效果实现如下

递归实现.png

画图说明

image.png

递归解题说明.png

解释：即递归至找到最后一个节点，然后依次将每一次递归时的当前节点的next的next指向自己，即将后一个节点的next指向自己。

迭代（非递归）实现实例代码如下

// 迭代(非递归)反转链表
- (LinkNode *)reverseList2:(LinkNode *)head {
    if (head == nil || head.next == nil) {
        return head;
    }
    
    LinkNode *newHead = nil;
    while (head) {
        LinkNode *tmp = head.next;
        head.next = newHead;
        newHead = head;
        head = tmp;
    }
    
    return newHead;
}

运行效果如下：