链表反转

题目：链表反转

/*
参考：https://blog.csdn.net/superxiaolong123/article/details/86687733
*/

@interface RCLinkedListNode : NSObject

@property (nonatomic, assign) NSInteger value;
@property (nonatomic, strong) RCLinkedListNode *next;

@end

@implementation RCLinkedListNode

@end

@implementation ViewController

- (void)p_reverseLinkedList {
    RCLinkedListNode *node = [self p_generateLinkedList:5];
    [self p_printLinkedList:node];
    RCLinkedListNode *reversed = [self p_reverse:node];
    [self p_printLinkedList:reversed];
}

//递归写法
- (RCLinkedListNode *)p_reverse2:(RCLinkedListNode *)header {
    if (header == nil || header.next == nil) {
        return header;
    }
    RCLinkedListNode *temp = header.next;//保持一下尾节点
    RCLinkedListNode *newHeader = [self p_reverse2:header.next];//缩小规模的链表
    temp.next = header;//连接尾节点和头
    header.next = nil;
    return newHeader;
}

//就地反转
- (RCLinkedListNode *)p_reverse:(RCLinkedListNode *)header {
    RCLinkedListNode *currentNode = header;
    RCLinkedListNode *newNode;
    while (currentNode) {
        RCLinkedListNode *tempNode = currentNode.next;
        currentNode.next = newNode;
        newNode = currentNode;
        currentNode = tempNode;
    }
    return newNode;
}

- (RCLinkedListNode *)p_generateLinkedList:(NSInteger)count {
    RCLinkedListNode *head = [RCLinkedListNode new];
    head.value = 0;
    RCLinkedListNode *lastNode = head;
    for (NSInteger i = 1; i < count; i++) {
        RCLinkedListNode *node = [RCLinkedListNode new];
        node.value = i;
        lastNode.next = node;
        lastNode = node;
    }
    return head;
}

- (void)p_printLinkedList:(RCLinkedListNode *)node {
    while (node) {
        NSLog(@"%ld", node.value);
        node = node.next;
    }
}
@end