翻转双链表

思路

有很多方法这个是交换每个结点的前后指针
还有递归
头/尾插法
利用栈的特性

复杂度

// 时间复杂度: O(n)
// 空间复杂度: O(1)

代码

- (void)reverseList
{
    
    //把tail指向头部结点 目的在于tail 和 head交换
    self.current = self.head;
    self.tail = self.current;
    
    //临时的变量 思路是交换每个结点的前后指针
    DSNode *previousNode = nil;
    DSNode *nextNode     = nil;
    while (self.current) {
        //把当前结点的后面的结点保存 防止链表断裂
        nextNode          = self.current.next;
        
        //下面两行代码交换指针 实现了
        //当前结点下个结点指向前驱结点
        self.current.next = previousNode;
        //当前界定啊的上个结点指向下个结点
        self.current.prior = nextNode;
        
        //前驱结点和当前结点后移一位
        //前驱结点指向当前结点
        previousNode      = self.current;
        //当前结点指向下个结点
        self.current      = nextNode;
    }
    //头部结点指向当前结点的前驱
    self.head = previousNode;
     
}

用图来描述他的过程

原始的双链表 和 翻转后的双链表

• 第一步： tail指针指向了head 所指向的结点

• 第二步：多次循环 交换结点前后指针 然后指针后移一位

1. 第一次循环

   
   

2. 第二次循环

   
   

3. 第三次循环

   
   
   

   4.第四次循环：

   
   
   注意下次循环因为current 结点指向nil， 所以结束，这个就是临界点。

• 第三步：head 指向 了node3也就是pre所指向的结点

注意：一些注意的地方代码都有注释。