【LeetCode链表相关】

一、相交链表LeetCode160

题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

解题思路

哈希表，先遍历链表A，放入hashset，再遍历链表B，遍历到第一个存在于hashset的节点即相交节点

注意，hashset有自动去重的功能，这里hashset使用的泛型是ListNode，也就是说，只有一个节点的val和next都相同时，才会被判定为相同的节点，这样才保证了正确性。

```Java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int c1=81;
        ListNode res=null;
HashSet<ListNode> set1=new HashSet<ListNode>();
     while(headA!=null)
     {
        set1.add(headA);
        headA=headA.next;
     }
     while(headB!=null)
     {
         if(set1.contains(headB))
         {
            res=headB;
            return res;
         }
         headB=headB.next;
     }
       
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

二、移除链表元素Leetcode203

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

解题思路

迭代法：创建一个虚拟节点(常用链表操作技巧，能避免处理野指针的问题)，按虚拟节点从头开始遍历，遇到需要删除的节点采用tmp.next=tmp.next.next进行删除即可

```Java
class Solution {
    public ListNode removeElements(ListNode head, int val) {
       if(head==null)
       {
           return head;
       }
       int c1=77;
       ListNode dummyHead= new ListNode(0);
       dummyHead.next=head;
       ListNode tmp=dummyHead;
       while(tmp.next!=null)
       {
           if(tmp.next.val==val)
           {
               tmp.next=tmp.next.next;
           }
           else
           {
               tmp=tmp.next;
           }
       }
       return dummyHead.next;


    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

三、将二叉树转换为链表(LeetCode114)

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

解题思路：

题目说展开后的单链表应该与前序遍历，很容易想到另起一个函数，先把前序遍历放入到ArrayList中，之后遍历ArrayList，将每个节点的left和right赋值即可

```Java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {

        List<TreeNode>l1=new ArrayList<TreeNode>();
        preOrderTraversal(root,l1);
        for(int i=0;i<l1.size()-1;i++)
        {
            if(l1.get(i)!=null)
            {
                l1.get(i).left=null;
                l1.get(i).right=l1.get(i+1);
            }

        }


    }
    public void preOrderTraversal(TreeNode root,List<TreeNode>l1)
    {
        if(root==null)
        {
            return ;
        }

            l1.add(root);
            preOrderTraversal(root.left,l1);
            preOrderTraversal(root.right,l1);
        
    }
    
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

四、环形链表(LeetCode142)

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

解题思路

双指针：这是一个小学追击问题，题目很好理解，两个任务：

• 链表是否有环
• 有环的话请给出入环的节点

因为针对这两任务，设置fast和slow两个指针，都指向head

指针一次走2步，慢指针一次走一步，相遇即存在环,即FristMeet

(任务1完成)

再设置一个指针SecondStart指向head，FristMeet一次走一步，SecondStart一次走一步，相遇即入环口

(任务2完成)

```Java
/**
 * 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)
        {
            return null;
        }
        ListNode tmp=head;
        ListNode fast=tmp;
        ListNode slow=tmp;
        ListNode FristMeet=null;
        ListNode SecondMeet=tmp;
        ListNode SecondStart=tmp;
        boolean tmp2=false;
        while(fast!=null)
        {
           if(fast==slow&&tmp2==true)
            {
                FristMeet=slow;
                break;
            } 
            slow=slow.next;
            tmp2=true;
            if(fast.next!=null)
            {
                fast=fast.next.next;
            }
            else
            {
                return null;
            }
        }
        if(FristMeet!=null)
        {
            while(SecondMeet!=null&&FristMeet!=null)
            {
                if(FristMeet==SecondMeet)
                {
                    break;
                }
                else
                {
                    FristMeet=FristMeet.next;
                    SecondMeet=SecondMeet.next;
                }
            }
        }
        return FristMeet;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

哈希表

哈希表的思路很好理解，先遍历一遍链表，当遍历到有节点已经存在HashSet时，即存在环，且这个节点就是入环节点

/**
 * 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)
        {
            return null;
        }
        HashSet set1=new HashSet<ListNode>();
        ListNode tmp=head;
        while(tmp.next!=null)
        {
            if(set1.contains(tmp))
            {
                return tmp;
            }
            set1.add(tmp);
            tmp=tmp.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31