【剑指Offer专题】链表系列：从尾到头打印链表、反转链表、回文链表、合并两个排序的链表（C++和Python实现）...

关注上方“深度学习技术前沿”&＃xff0c;选择“星标公众号”&＃xff0c;

资源干货&＃xff0c;第一时间送达&＃xff01;

输入一个链表的头节点&＃xff0c;从尾到头反过来返回每个节点的值&＃xff08;用数组返回&＃xff09;。

示例 1&＃xff1a;

输入&＃xff1a;head &＃61; [1,3,2]输出&＃xff1a;[2,3,1]

通常&＃xff0c;这种情况下&＃xff0c;我们不希望修改原链表的结构。返回一个反序的链表&＃xff0c;这就是经典的“后进先出”&＃xff0c;我们可以使用栈实现这种顺序。每经过一个结点的时候&＃xff0c;把该结点放到一个栈中。当遍历完整个链表后&＃xff0c;再从栈顶开始逐个输出结点的值&＃xff0c;给一个新的链表结构&＃xff0c;这样链表就实现了反转。

C&＃43;&＃43;实现&＃xff1a;

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {public:vector reversePrint(ListNode* head) {stack result;vector reverse;ListNode* nodes &＃61; head;while(nodes !&＃61;NULL){result.push(nodes->val);nodes &＃61; nodes->next;}while(!result.empty()){reverse.push_back(result.top());result.pop();}return reverse;}};

Python实现&＃xff1a;

# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val &＃61; x# self.next &＃61; Noneclass Solution:def printListFromTailToHead(self, listNode):# write code hereresult &＃61; []while listNode:result.insert(0, listNode.val)listNode &＃61; listNode.nextreturn result

反转一个单链表。

示例:

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

这个很简单&＃xff0c;我们使用三个指针&＃xff0c;分别指向当前遍历到的结点、它的前一个结点以及后一个结点。

在遍历列表时&＃xff0c;将当前节点的 next 指针改为指向前一个元素.

C&＃43;&＃43;&＃xff1a;

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {public:ListNode* reverseList(ListNode* head) {ListNode* pReversedHead &＃61; NULL;ListNode* pNode &＃61; head;ListNode* pPrev &＃61; NULL;while(pNode !&＃61; NULL){ListNode* pNext &＃61; pNode->next;if(pNext &＃61;&＃61; NULL){pReversedHead &＃61; pNode;}pNode->next &＃61; pPrev;pPrev &＃61; pNode;pNode &＃61; pNext;}return pReversedHead;}};

python:

# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val &＃61; x# self.next &＃61; Noneclass Solution:def reverseList(self, head: ListNode) -> ListNode:if not head or not head.next:return headlast &＃61; Nonewhile head:tmp &＃61; head.nexthead.next &＃61; lastlast &＃61; headhead &＃61; tmpreturn last

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2输出: false

示例 2:

输入: 1->2->2->1输出: true

复制链表值到数组列表中。

使用双指针法判断是否为回文。

遍历链表将值复制到数组列表中。用 currentNode 指向当前节点。每次迭代向数组添加 currentNode.val&＃xff0c;并更新 currentNode &＃61; currentNode.next&＃xff0c;当 currentNode &＃61; null 则停止循环。

在 Python 中&＃xff0c;很容易构造一个列表的反向副本&＃xff0c;也很容易比较两个列表。因此最好使用双指针法来检查是否为回文。我们在起点放置一个指针&＃xff0c;在结尾放置一个指针&＃xff0c;每一次迭代判断两个指针指向的元素是否相同&＃xff0c;若不同&＃xff0c;返回 false&＃xff1b;相同则将两个指针向内移动&＃xff0c;并继续判断&＃xff0c;直到相遇。

在编码的过程中&＃xff0c;注意我们比较的是节点值的大小&＃xff0c;而不是节点本身。正确的比较方式是&＃xff1a;node_1.val &＃61;&＃61; node_2.val。而 node_1 &＃61;&＃61; node_2 是错误的。

时间复杂度&＃xff1a;O(n)&＃xff0c;其中 n 指的是链表的元素个数。

第一步&＃xff1a;遍历链表并将值复制到数组中&＃xff0c;O(n)。

第二步&＃xff1a;双指针判断是否为回文&＃xff0c;执行了 O(n/2)次的判断&＃xff0c;即 O(n)。

总的时间复杂度&＃xff1a;O(2n) &＃61; O(n)。

空间复杂度&＃xff1a;O(n)&＃xff0c;其中 n 指的是链表的元素个数&＃xff0c;我们使用了一个数组列表存放链表的元素值。

# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val &＃61; x# self.next &＃61; Noneclass Solution:def isPalindrome(self, head: ListNode) -> bool:vals &＃61; []current_node &＃61; headwhile current_node is not None:vals.append(current_node.val)current_node &＃61; current_node.nextreturn vals &＃61;&＃61; vals[::-1]

输入两个单调递增的链表&＃xff0c;输出两个链表合成后的链表&＃xff0c;当然我们需要合成后的链表满足单调不减规则。

先判断输入的链表是否为空的指针。如果第一个链表为空&＃xff0c;则直接返回第二个链表&＃xff1b;如果第二个链表为空&＃xff0c;则直接返回第一个链表。如果两个链表都是空链表&＃xff0c;合并的结果是得到一个空链表。

两个链表都是排序好的&＃xff0c;我们只需要从头遍历链表&＃xff0c;判断当前指针&＃xff0c;哪个链表中的值小&＃xff0c;即赋给合并链表指针即可。使用递归就可以轻松实现。

C&＃43;&＃43;:

/*struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}};*/class Solution {public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2){//判断指针是否为空if(pHead1 &＃61;&＃61; NULL){return pHead2;}else if(pHead2 &＃61;&＃61; NULL){return pHead1;}ListNode* pMergedHead &＃61; NULL;if(pHead1->val val){pMergedHead &＃61; pHead1;pMergedHead->next &＃61; Merge(pHead1->next, pHead2);}else{pMergedHead &＃61; pHead2;pMergedHead->next &＃61; Merge(pHead1, pHead2->next);}return pMergedHead;}};

Python:

# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val &＃61; x# self.next &＃61; Noneclass Solution:# 返回合并后列表def Merge(self, pHead1, pHead2):# write code hereif not pHead1:return pHead2if not pHead2:return pHead1pMergeHead &＃61; Noneif pHead1.val

-END-

推荐阅读&＃xff1a;

【LeetCode】一文详解二叉树的三大遍历&＃xff1a;前序、中序和后序&＃xff08;python和C&＃43;&＃43;实现&＃xff09;

算法求职必备书籍-《剑指Offer》

你面试稳了&＃xff01;通关LeetCode刷题完整攻略&＃xff0c;省时又高效

既然来了&＃xff0c;给个在看可否&＃xff01;~