C++数据结构之链表详解( 二 )_生活百科

七、删除有序链表中重复节点双指针遇到相等的就跳过，最后要将最后一个节点置为空。
public ListNode deleteDuplicates(ListNode head) {if(head==null){return null;}ListNode prev=head;ListNode cur=head.next;while(cur!=null){if(prev.val==cur.val){cur=cur.next;}else{prev.next=cur;prev=cur;cur=cur.next;}}prev.next=cur;return head;}
八、环形链表先用set判断是否存在空间复杂度为O（N），不太符合题目要求
public boolean hasCycle(ListNode head) {HashSet<ListNode> set=new HashSet<>();while(head!=null){set.add(head);head=head.next;if(set.contains(head)){return true;}}return false;}
2.快慢指针数学问题，快指针走两步，慢指针走一步，有环一定相遇，没有环就不会相遇空间复杂度为O(1)
public boolean hasCycle(ListNode head) {//快慢指针还是数学问题if(head==null||head.next==null){return false;}ListNode slow=head;ListNode fast=head.next;while(slow!=fast){if(fast==null||fast.next==null){return false;}fast=fast.next.next;slow=slow.next;}return true;}
九、相交链表1.先利用set存储节点之后循环判断，空间复杂度为O（N）时间复杂度为O（N），比较慢
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {HashSet<ListNode>set=new HashSet<>();while(headA!=null){set.add(headA);headA=headA.next;}while(headB!=null){if(set.contains(headB)){return headB;}headB=headB.next;}return null;}
2.双指针，确实没想出来，看了题解才知道是两个链表相连接，遍历是否有想交的节点
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode cur1=headA;ListNode cur2=headB;while(cur1!=cur2){cur1=cur1==null?headB:cur1.next;cur2=cur2==null?headA:cur2.next;}return cur1;}
十、两数相加这道题没什么技巧，就是注意很多特殊情况，加完要判断进位，我第一次敲的时候能执行但是不能过，没有考虑到特殊情况。
最后看评论解答就是用一个进位标志数来解决，学到了。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode list=new ListNode(-1);ListNode head=list;int t=0;while(l1!=null||l2!=null||t!=0){if(l1!=null){t+=l1.val;l1=l1.next;}if(l2!=null){t+=l2.val;l2=l2.next;}list.next=new ListNode(t%10);list=list.next;t/=10;}return head.next;}
十一、回文链表1.可以将链表中值存放在顺序表中，之后定义双指针遍历判断
2.快慢指针带反转
3.利用栈实现li
public boolean isPalindrome(ListNode head) {//利用栈来实现回文结构Stack<Integer> stack=new Stack<>();ListNode cur=head;while(cur!=null){stack.push(cur.val);cur=cur.next;}ListNode cur1=head;while(cur1!=null){if(cur1.val!=stack.pop()){return false;}cur1=cur1.next;}return true;}
定义快慢指针，之后反转链表来实现
public boolean isPalindrome(ListNode head) {//快慢指针来反转链表if(head==null||head.next==null){return true;}ListNode fast=head;ListNode slow=head;while(fast.next!=null&&fast.next.next!=null){fast=fast.next.next;slow=slow.next;}//走到中间节点，反转链表slow=reverse(slow.next);while(slow!=null){if(head.val!=slow.val){return false;}head=head.next;slow=slow.next;}return true;}public ListNode reverse(ListNode head){//反转链表ListNode cur=head;ListNode curNext=head.next;cur=curNext;head.next=null;while(cur!=null){curNext=curNext.next;cur.next=head;head=cur;cur=curNext;}return head;}

文章插图

文章插图

总结本篇文章就到这里了，希望能给你带来帮助，也希望你能给多多关注趣讯吧的更多内容！