1 链表常规题目
链表常规题目:
2 链表反序
- 初始化:单链表需要指向一个前向节点:
- 反序:
2.1 代码示例
/**
* 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 *pre = NULL, *cur = head;
while(cur)
{
ListNode *next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
注意中间4步:https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
3 回文链表
-
利用快慢指针的思想:
- 快指针每次走两格,慢指针每次走一格,则快指针到终点时候,慢指针刚好在中间位置
- 反转后半部分链表:
- 比较值
class Solution { public boolean isPalindrome(ListNode head) { // 快慢指针找中点 ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // 反转后半部分 ListNode pre = null; while (slow != null) { ListNode next = slow.next; slow.next = pre; pre = slow; slow = next; } // 前后两段比较是否一致 ListNode node = head; while (pre != null) { if (pre.val != node.val) { return false; } pre = pre.next; node = node.next; } return true; } }
-
递归思想
class Solution { public: ListNode *root; bool flag = true; void dfs(ListNode *head){ if(head == NULL){ return ; } dfs(head->next); if(head->val != root->val){ flag = false; } root = root->next; } bool isPalindrome(ListNode* head) { root = head; dfs(head); return flag; } };
注意:https://leetcode-cn.com/problems/palindrome-linked-list-lcci/comments/
原文链接: https://www.cnblogs.com/lihaihui1991/p/14495518.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/400335
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!