剑指offer刷题总结——链表篇（一）

痛定思痛。 2021-09-21 03:14 342阅读 0赞

### 1.从尾到头打印链表 ###

**【题目】**

输入一个链表，按链表从尾到头的顺序返回一个 ArrayList。

**【代码】**

package swear2offer.linkednode;
    
    import java.util.ArrayList;
    
    public class ReturnArrayList { 
    
        /** * 输入一个链表，按链表从尾到头的顺序返回一个 ArrayList。 * */
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { 
    
            ArrayList<Integer> arrayList = new ArrayList<>();
    
            ListNode head = listNode;
    
            while(head != null) { 
                arrayList.add(0,head.val);
                head = head.next;
            }
    
            return arrayList;
        }
    
        public static void main(String[] args) { 
            ListNode node1,node2,node3;
            node1 = new ListNode(1);
            node2 = new ListNode(2);
            node3 = new ListNode(3);
    
            node1.next = node2;
            node2.next = node3;
    
            System.out.println(new ReturnArrayList().printListFromTailToHead(node1));
        }
    }

**【思路】**

利用动态数组arraylist的 **add(index,value)** 方法，遍历的时候，每次把数据都放在第一位

--------------------

### 2.链表中倒数第 k 个结点 ###

**【题目】**

输入一个链表，输出该链表中倒数第 k 个结点。

**【代码】**

package swear2offer.linkednode;
    
    public class Reciprocal { 
    
        /** * 输入一个链表，输出该链表中倒数第 k 个结点。 * * 双游标法，两个间距k-1的游标，当第二个游标到末尾的时候，第一个是倒数k * */
        public ListNode FindKthToTail(ListNode head,int k) { 
    
            if (head == null || k == 0) return null;
    
            int i;
            ListNode nodeI,nodeJ;
    
            nodeI = head;
            nodeJ = head;
            i = 1;
    
            while (nodeJ.next != null) { 
                while (i < k) { 
                    i++;
                    nodeJ = nodeJ.next;
                    if (nodeJ.next == null && i<k) return null;
                }
    
                /** * while循环中，经常需要对循环条件进行二次判断 * nodeJ != null * nodeJ.next != null 二者区别是否把最后一个节点算入其中计算 * */
                if (nodeJ.next != null) { 
                    nodeI = nodeI.next;
                    nodeJ = nodeJ.next;
                }
            }
    
            return nodeI;
        }
        
    
    
    }

**【思考】**

漏掉特殊情况：

*  空链表
 *  k ==0
 *  k大于链表长度

--------------------

### 3.反转链表 ###

**【题目】**

输入一个链表，反转链表后，输出新链表的表头。

**【代码】**

/** * 输入一个链表，反转链表后，输出新链表的表头。 * * 思路：遍历的时候，不断的解链，构造一个新的node作为后续链表的表头 * */
        public ListNode ReverseList(ListNode head) { 
    
            if (head == null) return null;
    
            if (head.next == null) return head;
    
            ListNode temp,index;
    
            temp = head.next;
            index = head.next;
            head.next = null;
    
            while (index.next != null) { 
                index = index.next;
                temp.next = head;
                head = temp;
                temp = index;
            }
    
            index.next = head;
    
            return index;
    
        }

【思考】

链表的特殊情况：

*  链表为空
 *  链表只有一个元素

--------------------

### 4.合并两个排序的链表 ###

**【题目】**

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

**【代码】**

package swear2offer.linkednode;
    
    public class Merge { 
    
        /** * 输入两个单调递增的链表，输出两个链表合成后的链表， * 当然我们需要合成后的链表满足单调不减规则。 * */
        public ListNode Merge(ListNode list1,ListNode list2) { 
    
            ListNode newNode,index;
    
            if (list1 == null) return list2;
            else if (list2 == null) return list1;
            else { 
    
                // 把新链表的头节点进行赋值
                if (list1.val > list2.val){ 
                    newNode = list2;
                    list2 = list2.next;
                } else { 
                    newNode = list1;
                    list1 = list1.next;
                }
    
                // 新链表的索引
                index = newNode;
    
    
                // list1和list2 任何一个为空就跳出循环
                while(list1!=null && list2!=null) { 
                    if (list1.val > list2.val) { 
                        index.next = list2;
                        list2 = list2.next;
    
                    } else { 
                        index.next = list1;
                        list1 = list1.next;
                    }
                    index = index.next;
                }
    
                if (list1 != null) index.next = list1;
    
                if (list2 != null) index.next = list2;
    
                return newNode;
            }
    
        }
    
    }

### 5.两个链表的第一个公共结点 ###

**【题目】**

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

**【代码】**

/** * 输入两个链表，找出它们的第一个公共结点。 * （注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的） * */
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { 
            if (pHead1 == null || pHead2 == null) return null;
    
            ListNode p1,p2,res;
            p1 = pHead1;
            while (p1 != null) { 
                p2 = pHead2;
                while (p2 != null) { 
                    if (p1 == p2) { 
                        res = p1;
                        return res;
                    } else { 
                        p2 = p2.next;
                    }
                }
                p1 = p1.next;
            }
    
            return null;
        }

**【思考】**

巧妙方法：

看下面的链表例子：  
0-1-2-3-4-5-null  
a-b-4-5-null  
如果两个链表连接之后，长度就变成一样了。  
如果有公共结点，那么指针一起走到末尾的部分，也就一定会重叠。看看下面指针的路径吧。  
p1： 0-1-2-3-4-5-null (连接)-a-b-4-5-null  
p2: a-b-4-5-null (连接) 0-1-2-3-4-5-null  
因此，两个指针所要遍历的链表就长度一样了！  
如果两个链表存在公共结点，那么 p1 就是该结点，如果不存在那么 p1 将会是 null。

**【代码】**

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { 
            if(pHead1 == null || pHead2 == null)return null;
            ListNode p1 = pHead1;
            ListNode p2 = pHead2;
            while(p1!=p2){ 
                p1 = p1.next;
                p2 = p2.next;
                if(p1 != p2){ 
                    if(p1 == null)p1 = pHead2;
                    if(p2 == null)p2 = pHead1;
                }
            }
            return p1;
        }