链表的部分OJ题目

古城微笑少年丶 2022-11-10 10:39 169阅读 0赞

### 链表的部分OJ题目 ###

*  移除链表元素
 *  反转链表
 *  链表的中间结点
 *  链表中倒数第K个结点
 *  合并两个有序链表
 *  链表分割
 *  删除链表中重复结点
 *  相交链表
 *  链表的回文结构
 *  环形链表
 *  环形链表2

# 移除链表元素 #

LeetCode-203 [移除链表元素][Link 1]  
203. 移除链表元素  
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 **新的头节点** 。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]

class Solution { 
            public ListNode removeElements(ListNode head, int val) { 
            //头插一个哨兵结点
            ListNode newHead = new ListNode(-1);
            newHead.next = head;
            ListNode prev = newHead;
            while (prev.next != null) { 
                if (prev.next.val == val) { 
                    prev.next = prev.next.next;
                } else { 
                    prev = prev.next;
                }
            }
            return newHead.next;
        }
    }

# 反转链表 #

LeetCode-206 [反转链表][Link 2]  
反转一个单链表。  
示例:  
输入: 1->2->3->4->5->NULL  
输出: 5->4->3->2->1->NULL

class Solution { 
        public ListNode reverseList(ListNode head) { 
    
            ListNode prev = null;
            ListNode cur = head;
            while (cur != null) { 
                ListNode next = cur.next;
    
                cur.next = prev;
                prev = cur;
                cur = next;
            }
            return prev;
        }
    }

# 链表的中间结点 #

LeetCode-876 [链表的中间结点][Link 3]  
链表的中间结点  
给定一个头结点为 head 的非空单链表，返回链表的中间结点。  
如果有两个中间结点，则返回第二个中间结点。

class Solution { 
        public ListNode middleNode(ListNode head) { 
            ListNode fast = head;
            ListNode slow = head;
    
            while (fast != null) { 
                fast = fast.next;
                if (fast == null) { 
                    break;
                }
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }

# 链表中倒数第K个结点 #

nowcoder剑指offer[链表中倒数第K个结点][K]  
题目描述  
输入一个链表，输出该链表中倒数第k个结点。

class Solution { 
        public ListNode FindKthToTail(ListNode head, int k) { 
            ListNode fast = head;
            ListNode slow = head;
            for (int i = 0; i < k; i++) { 
                if (fast != null) { 
                    fast = fast.next;
                } else { 
                    return null;
                }
            }
            while (fast != null) { 
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }

# 合并两个有序链表 #

LeetCode-21 [合并两个有序链表][Link 4]  
合并两个有序链表  
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
            ListNode newHead = new ListNode(-1);
            ListNode p = newHead;
            ListNode last1 = l1;
            ListNode last2 = l2;
    
            while (last1 != null && last2 != null) { 
                if (last1.val <= last2.val) { 
                    p.next = last1;
                    p = p.next;
                    last1 = last1.next;
                } else { 
                    p.next = last2;
                    p = p.next;
                    last2 = last2.next;
                }
            }
            if (last1 == null) { 
                p.next = last2;
            } else { 
                p.next = last1;
            }
            return newHead.next;
        }
    }

# 链表分割 #

nowcoder程序员面试宝典 [链表分割][Link 5]  
题目描述  
现有一链表的头指针 ListNode\* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

class Partition { 
        public ListNode partition(ListNode pHead, int x) { 
            ListNode l1 = new ListNode(-1);
            ListNode l2 = new ListNode(-1);
            ListNode last1 = l1;
            ListNode last2 = l2;
            ListNode cur = pHead;
            while (cur != null) { 
                if (cur.val < x) { 
                    last1.next = cur;
                    last1 = last1.next;
                    cur = cur.next;
                } else { 
                    last2.next = cur;
                    last2 = last2.next;
                    cur = cur.next;
                }
            }
            last2.next = null;
            last1.next = l2.next;
            return l1.next;
        }
    }

# 删除链表中重复结点 #

nowcoder剑指offer [删除链表中重复结点][Link 6]  
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

class Solution { 
        public ListNode deleteDuplication(ListNode pHead) { 
            if (pHead == null) { 
                return null;
            }
            ListNode newHead = new ListNode(-1);
            newHead.next = pHead;
            ListNode prev = newHead;
            ListNode cur = pHead;
            ListNode next = cur.next;
    
            while (next != null) { 
                if (cur.val != next.val) { 
                    prev = prev.next;
                    cur = cur.next;
                    next = next.next;
                } else { 
                    while (next != null && cur.val == next.val) { 
                        next = next.next;
                    }
                    prev.next = next;
                    cur = next;
                    if (next != null) { 
                        next = next.next;
                    }
                }
    
            }
            return newHead.next;
        }
    }

# 相交链表 #

LeetCode\_160[相交链表][Link 7]  
编写一个程序，找到两个单链表相交的起始节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]  
思路：  
首先判断是否为相交节点，然后从相同长度起往后走，判断指向的对象是否相同，找到相交节点。

class Solution { 
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
            if (headA == null || headB == null) { 
                return null;
            }
            ListNode cur1 = headA;
            ListNode cur2 = headB;
            int count1 = 0;
            int count2 = 0;
            while (cur1.next != null) { 
                count1++;
                cur1 = cur1.next;
            }
            while (cur2.next != null) { 
                count2++;
                cur2 = cur2.next;
            }
            if (cur1.equals(cur2)) { 
                int n = count1 - count2;
                cur1 = headA;
                cur2 = headB;
                if (n > 0) { 
                    for (int i = 0; i < n; i++) { 
                        cur1 = cur1.next;
                    }
                } else if (n < 0) { 
                    for (int i = 0; i < -n; i++) { 
                        cur2 = cur2.next;
                    }
                }
                while (cur1 != null && cur2 != null) { 
                    if (cur1.equals(cur2)) { 
                        return cur1;
                    } else { 
                        cur1 = cur1.next;
                        cur2 = cur2.next;
                    }
                }
                return null;
            } else { 
                return null;
            }
        }
    }

# 链表的回文结构 #

nowcoder [链表的回文结构][Link 8]  
题目描述  
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

思路：  
首先找到中间节点，然后将后面的链表逆置，然后从头开始比较判断  
（可能不是最优解，欢迎补充）

public class PalindromeList { 
        public boolean chkPalindrome(ListNode A) { 
            // write code here
            ListNode fast=A;
            ListNode slow=A;
            
            while (fast!=null){ 
                fast=fast.next;
                if (fast==null){ 
                    break;
                }
                fast=fast.next;
                slow=slow.next;
            }
            ListNode reverse = reverse(slow.next);
            ListNode cur=A;
            while (reverse!=null){ 
                if (reverse.val==cur.val){ 
                    reverse=reverse.next;
                    cur=cur.next;
                }else { 
                    return false;
                }
            }
            return true;
        }
    
        public ListNode reverse(ListNode head) { 
            ListNode prev = null;
            ListNode cur = head;
            while (cur != null) { 
                ListNode next = cur.next;
    
                cur.next = prev;
                prev = cur;
                cur = next;
            }
            return prev;
        }
    }

# 环形链表 #

LeetCode-p141 [环形链表][Link 9]  
判断链表中是否有环：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]

class Solution { 
        public boolean hasCycle(ListNode head) { 
            if (head==null){ 
                return false;
            }
            ListNode fast = head;
            ListNode slow = head;
    
            while (fast.next != null) { 
                fast = fast.next;
                if (fast.next == null) { 
                    return false;
                }
                fast = fast.next;
                slow = slow.next;
                if (fast.equals(slow)) { 
                    return true;
                }
            }
            return false;
        }
    }

# 环形链表2 #

LeetCode-p142 [环形链表2][2]  
环形链表，并找到入环第一个点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 4]

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
    public class Solution { 
        public ListNode detectCycle(ListNode head) { 
            if (head == null || head.next == null) { 
                return null;
            }
            boolean flg = false;
            ListNode fast = head;
            ListNode slow = head;
            while (fast.next != null) { 
                fast = fast.next;
                if (fast.next == null) { 
                    return null;
                }
                fast = fast.next;
                slow = slow.next;
                if (fast.equals(slow)) { 
                    flg = true;
                    break;
                }
            }
            if (flg) { 
                slow = head;
                while (!slow.equals(fast) && fast != null) { 
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }else { 
                return null;
            }
        }
    }

[Link 1]: https://leetcode-cn.com/problems/remove-linked-list-elements/description/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221023/049a615d38304791a6af6662bf88084c.png
[Link 2]: https://leetcode-cn.com/problems/reverse-linked-list/description/
[Link 3]: https://leetcode-cn.com/problems/middle-of-the-linked-list/description/
[K]: https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a
[Link 4]: https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: /images/20221023/8e5308e2b1734416abeeadbb95465cdd.png
[Link 5]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70
[Link 6]: https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef
[Link 7]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]: /images/20221023/abce94b8b2eb49189987e06d271e5164.png
[Link 8]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa
[Link 9]: https://leetcode-cn.com/problems/linked-list-cycle/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]: /images/20221023/98e40f8b35544e5ca21ea724c6e3e8b1.png
[2]: https://leetcode-cn.com/problems/linked-list-cycle-ii/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 4]: /images/20221023/923e39556e6748ab86d3d98f523af9b4.png